Vybrané kapitoly z diskrétnej matematiky

1. Rozhodnite, či sú grafy G1 až G10 Eulerovské, Hamiltonovské grafy, alebo aj aj.

2.Ktoré z nasledujúcich grafov sú eulerovské grafy:

a)      Kompletný graf K6

b)      Bipartitný graf K6,6

c)      Graf- cyklus C6

d)      Graf – cesta P6

e)      Dodecahedron

3. Rozdeľte graf na cykly tak, aby cykly nemali spoločné žiadne hrany.

4. Pokúste sa vyriešiť problém siedmych mostov:

a)      Aby sme začali a skončili na rovnakom brehu

b)      Aby sme začali a skončili na hocijakom brehu

5. Ktoré z nasledujúcich grafov sú Hamiltonovske grafy:

a)      Bipartitný graf K4,4

b)      strom

6. Nájdite Hamiltonov cyklus v grafe, ktorý začína písmenami

a)      BCPNM

b)      JVTSR

c)      BCD a zároveň končí v T

7. Môže kôň na šachovnici prejsť každým políčkom práve raz a skončiť tam, kde začal? (Šachovnica má rozmery 8x8, kôň sa môže presúvať dve polička horizontálne/vertikálne a jedno políčko kolmo na smer)?

 

8. Labyrint – vytvorte graf, ktorý predstavuje všetky možnosti (cesty) ako sa dostať z labyrintu.

9. Ukážte, že eulerovský graf neobsahuje mosty.

10. Charakterizujte grafy, ktoré možno nakresliť dvoma otvorenými ťahmi.

11. Dokážte: ak súvislý graf má  vrcholov nepárneho stupňa, tak ho možno nakresliť práve  rôznymi ťahmi ale nie menej otvorenými ťahmi.

12. Dokážte, že ak graf s aspoň tromi vrcholmi obsahuje most, tak obsahuje aj artikuláciu.

13. Dokážte, že v Petersenovom grafe neexistuje hamiltonovská kružnica.

14. Dokážte, že ak v Petersenovom grafe odstránime jeden vrchol, tak v takom grafe už existuje hamiltonovská kružnica.

15. Ukážte, že graf na obrázku  nemá hamiltonovskú kružnicu.

16. Dokážte, že graf obsahujúci dva nesusedné vrcholy tretieho stupňa a všetky ostatné  druhého stupňa, nemá hamiltonovskú kružnicu.

17. Ukážte, že graf predstavuje mnohosten.

18.  Na základe tvrdenia E. Jucoviča ukážte, že graf z predchádzajúceho cvičenia je hamiltonovský.