Bevezetés a számításelméletbe

12. gyakorlat, 2002. december 2.
 
 

Gráfok, fák  

  1. Egy gráf pontjai 3 hosszú $b_1, b_2, b_3$ bitsorozatok. Két pontot akkor és csak akkor köt össze él, ha a nekik megfelelő bitsorozatok egymásból forgatással megkaphatóak. (A $b_1, b_2, b_3$ sorozat elforgatottja a $b_3, b_1, b_2$.) Rajzoljuk le a gráfot! Egyszerű-e, illetve összefüggő-e az így kapott gráf?

  2. Legfeljebb hány éle lehet egy $n$ pontú egyszerű gráfnak?

  3. Hány éle van egy $n=2k$ pontú 3-reguláris gráfnak?

  4. Létezik olyan 3-reguláris gráf, aminek páratlan sok pontja van?

  5. Az előre megszámozott (címkézett) $n$ pont közé hányféleképpen húzhatunk be élet úgy, hogy egyszerű gráfhoz jussunk?

  6. Létezik-e egyszerű gráf, melyben a pontok foka rendre
    1. 1,2,2,3,3,3;
    2. 2,3,3,4,5,6,7;
    3. 1,1,2,2,3,4,4;
    4. 1,1,3,3,3,3,5,6,8,9?

  7. Egy körmentes gráf (erdő) $k$ komponensből áll. Hány éle van a gráfnak?

  8. Egy negyedfokú reguláris összefüggő gráfból töröljük egy feszítőfa éleit. Bizonyítsuk be, hogy a maradék legalább két kört tartalmaz!

  9. Az alábbi állítások közül melyik ekvivalens azzal, hogy ``a $G(V,E)$ gráf fa''?

    1. $G$ egyszerű, összefüggő és legalább két elsőfokú pontot tartalmaz;
    2. $G$ bármely két pontja között pontosan egy út van;
    3. HF $G$ összefüggő, de bármelyik élét elhagyva szétesik több komponensre;
    4. HF $\vert E\vert=\vert V\vert-1$;
    5. HF $G$ körmentes, de nem lehet hozzávenni új élet a körmentesség megtartásával.

  10. HF Milyen komponensekből állhat egy olyan gráf, melyben a $\Delta$ maximális fokszám 2 ?

  11. HF Hány 3 hosszú kör található abban a gráfban, amelyet az $n$-pontú $K_n$ teljes gráfból kapunk, ha egy élét elhagyjuk?

  12. HF Igazoljuk, hogy egy gráf és komplementere közül legalább az egyik összefüggő.

  13. HF Hány olyan páronként nem izomorf 6 pontú összefüggő egyszerű gráf létezik, melyben két másodfokú és négy harmadfokú pont van?

  14. HF Mutassunk olyan öt pontú gráfot, mely izomorf a komplementerével!

  15. HF Létezik-e hat pontú gráf is, amely izomorf a komplementerével?



Fogaras Daniel 2002-12-02