Bevezetés a számításelméletbe II.
2. gyakorlat 2002. február 21-22.
Csütörtök 10-12 IB-140 és péntek 8-10 IB-145
 
 
Hamilton-körök, páros gráfok és párosítások

 

1. Bejárható-e egy $7\times7$-es sakktábla összes mezője egy huszárral úgy, hogy a kiinduló helyre visszatérjünk és minden mezőt pontosan egyszer látogassunk meg? (Segítség: Fogalmazzuk meg a feladatot a gráfok nyelvén, és vegyük észre, hogy nem akármilyen gráfról van szó.)

2. Melyik igaz az alábbi állítások közül?
   1. Ha egy gráfnak páros sok pontja van és tartalmaz Hamilton-kört, akkor található benne teljes párosítás.
   2. Ha egy páros gráfnak van Hamilton-köre, akkor van benne teljes párosítás. (ZH példa, 2000 április)
   3. Ha egy gráfban van két éldiszjunkt (közös élt nem tartalmazó) teljes párosítás, akkor van benne Hamilton-kör.

3. 1. Az $n$-pontú $K_n$ teljes gráfból elhagytuk egy feszítőfa éleit, majd visszaraktunk két élet. Mutassuk meg, hogy az így nyert gráfban van Hamilton-kör.
   2. HF Bizonyítsuk be, hogy ha egy $n$ pontú egyszerű gráfnak ${{n-1}\choose{2}}+2$ éle van, akkor van benne Hamilton-kör. Igaz-e ez ${{n-1}\choose{2}}+1$ pontú gráfokra is?

4. Bizonyítsuk be, hogy tetszőleges $r$-reguláris páros gráf tartalmaz teljes párosítást.

5. Egy $G=(A,B,E)$ páros gráfban az $A$ független halmazba eső $X\subseteq A$ részhalmaz összes csúcsa lefedhető egyetlen $M$ párosítással. Hasonlóképp, létezik olyan $M'$ párosítás, amely az $Y\subseteq B$ részhalmazba tartozó összes pontot lefedi. Bizonyítsuk be, hogy létezik olyan $M''$ párosítás, amely lefedi az $X\cup Y$ összes pontját. (ZH-feladat, 1999 április)

6. HF A ping-pong VB csapatbajnokságának döntőjét Kína és Japán játsza egymással. Mindegyik csapatban 10 ember van és mindenki összesen 5 meccset játszik az ellenkező ország különböző játékosaival. A közönség szavazatai alapján dől el, hogy melyik játékos kerüljön össze melyikkel. Bizonyítsuk be, hogy a közönség bármilyen döntése mellett megszervezhető 5 fordulóban a döntő. (Egy fordulóban egy játékos legfeljebb egy meccset játszhat.)

7. HF Egy társaságban bármely két embernek legalább két közös ismerőse van. Tudjuk továbbá, hogy bármely két ember vagy ismeri egymást, vagy ha nem, akkor a társaság bármely harmadik tagját legalább az egyikük ismeri. Bizonyítsuk be, hogy a társaság tagjai leültethetők egy (megfelelő méretű) kerek asztal köré úgy, hogy mindenki két ismerőse között üljön. (ZH példa, 2000 április)

8. HF Egy páros gráf egyik pontosztályában van olyan $X$ részhalmaz, amelyre $\vert N(X)\vert\leq \vert X\vert-2$. Bizonyítsuk be, hogy nincs a gráfban Hamilton-út.