S5: Eulerovské a Hamiltonovské grafy
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ý.
- 26 februára 2016, 00:07
- 26 februára 2016, 00:07
- 26 februára 2016, 00:07
- 26 februára 2016, 00:07
- 16 marca 2016, 07:59