Bevezetés a számításelméletbe II.
1. gyakorlat 2002. szeptember 14-15.
Csütörtök 10-12 IB-140 és péntek 8-10 IB-145
 
 
Euler- és Hamilton-körök

 

1. Mely $n$-re létezik az $n$-pontú teljes gráfnak Hamilton-köre, Hamilton-útja, Euler-köre illetve Euler-útja?

2. Legalább hány élet kell hozzávenni a Petersen-gráfhoz, hogy legyen benne Euler-út?

3. Bizonyítsuk be, hogy bármely összefüggő gráf élei bejárhatók úgy, hogy minden élen pontosan kétszer haladunk végig!

4. Bizonyítsuk be, hogy egy 6-reguláris gráf élei irányíthatóak úgy, hogy minden pont kifoka és befoka is 3 legyen.

5. Van-e Hamilton-kör vagy -út az alábbi gráfban?
   

6. Bizonyítsuk be, hogy ha egy összefüggő $G$ gráf egy $K$ köréből egy élt törölve $G$ egy leghosszabb útját kapjuk, akkor $K$ a gráf Hamilton-köre!

7. HF Az $n$ és $k$ számokhoz tartozó $\hbox{{\it G}}_{n,k}$ Kneser-gráf pontjai egy $n$-elemű halmaz $k$-elemű részhalmazainak felelnek meg és két pont között pontosan akkor van él, ha a pontoknak megfelelő részhalmazok diszjunktak. Van-e Hamilton-kör
   1. $\hbox{{\it G}}_{6,3}$-ban, illetve
   2. $\hbox{{\it G}}_{16,3}$-ban?

8. HF Igazoljuk, hogy ha egy gráf minden pontjának foka páros, akkor kijelölhető a gráfban valahány kör úgy, hogy minden él pontosan egy körben szerepeljen!

9. HF Hány Hamilton-kört tartalmaz az $n$-pontú teljes gráf?

10. HF Egy gráf minden pontjának foka páros. Bizonyítsuk be, hogy a gráf minden vágása páros sok élet tartalmaz.

11. HF (*) Mutassuk meg, hogy egy teljes gráf éleit bárhogyan irányítjuk, az irányítások révén nyert gráfban lesz irányított Hamilton-út!