Bevezetés a számításelméletbe II.
1. gyakorlat 2003. február 13.
 
 
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. Minimálisan hányszor kell felemelni a ceruzánkat, hogy a Petersen-gráfot lerajzoljuk úgy, hogy minden élen teljes hosszában pontosan egyszer haladjunk végig?
3. 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.
4. Van-e Hamilton-kör vagy -út az alábbi gráfokban?
   
   
   
   
   
   
   
   
5. 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.
6. 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?
7. 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!
8. HF Hány Hamilton-kört tartalmaz az $n$-pontú teljes gráf?
9. 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.
10. HF Melyik igaz, melyik hamis az alábbi állítások közül?
    1. Ha egy összefüggő gráfban létezik Euler-út, és hozzáveszünk kört alkotó éleket, akkor az így nyert gráfban is létezik Euler-út.
    2. Ha egy gráfban létezik Euler-kör, és a gráf egy körének éleit töröljük, akkor az így nyert gráfban is létezik Euler-kör.
11. HF A $G_n$ egyszerű gráf csúcsait feleltessük meg az $n$-hosszú 0-1 bitsorozatoknak. Mely $n\ge 3$ esetén tartalmaz Euler-kört, illetve Hamilton-kört $G_n$, amelyben két csúcs között pontosan abban az esetben fut él, ha
    1. a megfelelő bitsorozatok pontosan egy bitben térnek el egymástól;
    2. a megfelelő bitsorozatok pontosan két bitben térnek el egymástól;
    3. a megfelelő bitsorozatok legalább két bitben térnek el egymástól?
12. HF Igazoljuk, hogy egy tetszőleges összefüggő gráf élei bejárhatóak úgy, hogy minden élen pontosan kétszer haladjunk végig.
13. 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!