Hamiltonovské grafy, planárnosť grafov, miery neplanárnosti

Ciele
  1. Hamiltonovské grafy.
  2. Mosty a artikulácie.
  3. Nutné podmienky hamiltonovskosti grafov.
  4. Problém obchodného cestujúceho.
  5. Planárnosť grafov.
  6. Homeomorfizmus grafov a Kuratowského veta.
Úvod
    1. Prvá časť toho cvičenia bude venovaná hamiltonovskosti grafov, overovaniu niektorých nutných podmienok a Problému obchodného cestujúceho, ktorý je vlastne aplikáciou hamiltonovských grafov.
    2. Druhá časť sa bude zaoberať planárnosťou grafov. Precvičované budú hlavne dve základné vety a to Eulerova a Kuratowského. Na záver sú zaradené jednoduché príklady týkajúce sa overovania planárnosti grafov.
    3. Pre úspešné zvládnutie toho cvičenia sa predpokladajú teoretické vedomosti prezentované na prednáške. Je dôležité, aby študent poznal základné definície a znenia dôležitých viet uvedených na prednáške.
Postup
  1. Príklad: V grafe danom nasledujúcim diagramom určte všetky mosty.
    Zobraziť riešenie
  2. Príklad: V grafe z predchádzajúcej úlohy určte všetky artikulácie.
    Zobraziť riešenie
  3. Príklad: Načrtnite diagram ľubovoľného grafu, ktorý obsahuje
    1. artikuláciu, ale nie most,
    2. most, ale nie artikuláciu,
    3. aj most, aj artikuláciu.
    Zobraziť riešenie
  4. Príklad: Na 16-tich vrcholoch zostrojte pravidelný súvislý graf 3. stupňa
    1. bez mosta
    2. s mostom
    Zobraziť riešenie
  5. Príklad: Zistite, či grafy \(G_1\), \(G_2\), \(G_3\) určené diagramami sú hamiltonovské. Ak áno, vyznačte hamiltonovskú kružnicu, ak nie, zdôvodnite prečo.
    Zobraziť riešenie
  6. Príklad: V grafe danom nasledujúcim diagramom riešte problém obchodného cestujúceho pomocou rozhodovacieho stromu.
    Zobraziť riešenie
  7. Príklad: Je daný súvislý planárny graf \(G\), ktorý má 11 vrcholov. Vieme, že odobratím 5 hrán dostaneme jeho kostru. Koľko hrán má daný graf?
    Zobraziť riešenie
  8. Príklad: Overte planárnosť grafu daného nasledujúcim diagramom.
    Zobraziť riešenie
  9. Príklad: Overte planárnosť grafu daného nasledujúcim diagramom.
    Zobraziť riešenie
  10. Príklad: Overte planárnosť grafu daného nasledujúcim diagramom.
    Zobraziť riešenie
Zdroje
  1. Klešč M.: Diskrétna matematika, Košice, 2006.
  2. Bučko M. - Klešč, M.: Diskrétna matematika, Elfa, Košice, 1999.
  3. Klešč M. - Plavka, J.: Grafové algoritmy a formálna logika, Košice 2008.
  4. Matoušek J. - Nešetřil J.:Kapitoly z diskrétní matematiky, Matfyzpress, Praha 1996.
Doplňujúce úlohy
    Úloha: Zistite, ktoré z grafov daných nasledujúcimi diagramami, sú, resp. nie sú hamiltonovské. Ak sú hamiltonovské, nájdite hamilt. kružnicu, ak nie sú hamiltonovské, zdôvodnite prečo.
    Úloha: V grafoch, ktoré sú dané nasledujúcimi diagramami riešte problém obchodného cestujúceho pomocou rozhodovacieho stromu.
    Úloha: Pokúste sa zdôvodniť, prečo grafy dané nasledujúcimi diagramami nie sú planárne.
    Úloha: Zistite, ktoré z grafov daných nasledujúcimi diagramami, sú, resp. nie sú planárne. Svoje tvrdenia zdôvodnite.
comments powered by Disqus