Čo je graf
Graf je dvojica G = (V, E), kde V je neprázdna množina vrcholov a E množina hrán — neusporiadaných dvojíc vrcholov. Hrana {u, v} spája vrcholy u a v; vtedy hovoríme, že sú susedné.
Štyri vrcholy, päť hrán
Vpravo je graf so štyrmi vrcholmi A, B, C, D. Hrán je |E| = 5 — štvorec plus jedna uhlopriečka.
Neorientovaný vs. orientovaný
V neorientovanom grafe je hrana neusporiadaná dvojica. V orientovanom (digrafe) má hrana smer — je to usporiadaná dvojica (u, v), šípka z u do v.
Slučka a násobná hrana
Slučka spája vrchol so sebou samým: {v, v}. Násobná hrana je viac hrán medzi tými istými dvoma vrcholmi.
Jednoduchý graf
Graf bez slučiek a bez násobných hrán. Väčšina viet teórie grafov sa formuluje práve preň.
Počet vrcholov |V| = n nazývame rád grafu, počet hrán |E| = m jeho veľkosť. V jednoduchom grafe je hrán najviac C(n, 2) = n(n−1)/2.
Vyber správnu odpoveď.
Stupeň vrcholu
Stupeň vrcholu deg(v) je počet hrán, ktoré v ňom incidujú (slučka sa počíta dvakrát). Vrcholu so stupňom 0 hovoríme izolovaný.
Veta o podaní rúk
Súčet stupňov všetkých vrcholov je dvojnásobok počtu hrán:
∑v∈V deg(v) = 2|E|
Dôsledok
Počet vrcholov nepárneho stupňa je v každom grafe párny (nikdy ich nie je nepárny počet).
Keď si na večierku všetci podajú ruky, každé podanie zvýši počet „podaní" presne dvom ľuďom. Preto je súčet podaní párny — a počet ľudí s nepárnym počtom podaní musí byť párny.
Graf so 4 vrcholmi stupňov 2, 2, 3, 3. Koľko má hrán? Klikaj.
Vyber správnu odpoveď.
Špeciálne grafy
Niekoľko rodín grafov sa vyskytuje tak často, že majú vlastné mená a značky.
Úplný graf
Každé dva vrcholy sú spojené hranou. Má C(n, 2) = n(n−1)/2 hrán, každý vrchol stupňa n − 1. Napr. K₅ má 10 hrán.
Cesta
Vrcholy v rade za sebou. Cesta Pₙ na n vrcholoch má n − 1 hrán; krajné vrcholy majú stupeň 1, vnútorné stupeň 2.
Kružnica
Uzavretý cyklus. Kružnica Cₙ má n hrán a každý vrchol stupňa práve 2.
Bipartitný graf
Vrcholy sa dajú rozdeliť do dvoch častí tak, že každá hrana ide medzi nimi (nikdy vnútri). Bipartitný graf neobsahuje nepárnu kružnicu.
Podgraf
Graf H je podgrafom G, ak V(H) ⊆ V(G) a E(H) ⊆ E(G). Vznikne vynechaním niektorých vrcholov a hrán.
Doplnok
Doplnok Ḡ má tie isté vrcholy, ale hrany práve tam, kde ich G nemá. Spolu dajú úplný graf: G ∪ Ḡ = Kₙ.
Kₙ: n(n−1)/2 · Pₙ: n − 1 · Cₙ: n. Tieto tri vzorce sa hodia v takmer každej úlohe.
Klikni a over si výsledok.
Vyber správnu odpoveď.
Sledy, ťahy, cesty a súvislosť
Pohyb po hranách z vrcholu do vrcholu opisujeme troma pojmami, ktoré sa líšia tým, čo sa smie opakovať.
Sled
Striedavá postupnosť vrcholov a hrán. Vrcholy aj hrany sa smú opakovať. Najvšeobecnejší pojem.
Ťah
Sled, v ktorom sa neopakuje žiadna hrana (vrcholy áno). Po každej hrane prejdeme nanajvýš raz.
Cesta
Sled, v ktorom sa neopakuje žiadny vrchol (a teda ani hrana). Najprísnejší pojem.
Každá cesta je aj ťahom a každý ťah je aj sledom — opačne to neplatí. Pomôcka: cesta ⊆ ťah ⊆ sled.
Graf je súvislý, ak medzi každou dvojicou vrcholov existuje cesta. Ak nie je súvislý, rozpadá sa na komponenty súvislosti — maximálne súvislé časti. Vzdialenosť d(u, v) je dĺžka (počet hrán) najkratšej cesty z u do v.
Vyber správnu odpoveď.
Eulerovské a hamiltonovské grafy
Eulerov ťah prejde každú hranu grafu práve raz. Hamiltonovská kružnica navštívi každý vrchol práve raz a vráti sa späť.
Eulerov ťah (Eulerova veta)
Súvislý graf má otvorený Eulerov ťah ⇔ má presne 2 vrcholy nepárneho stupňa. Uzavretý Eulerov ťah (kružnicu) má ⇔ majú všetky vrcholy párny stupeň (0 nepárnych).
Königsberské mosty
Klasická úloha: prejsť 7 mostov mesta práve raz. Graf má 4 vrcholy nepárneho stupňa ⇒ Eulerov ťah neexistuje. Tým Euler založil teóriu grafov.
Eulerov ťah je o hranách a má jednoduché kritérium cez stupne. Hamiltonovská kružnica je o vrcholoch a žiadne ľahké kritérium nemá — rozhodnúť jej existenciu je výpočtovo ťažký problém.
Vyber správnu odpoveď.
Záverečný kvíz
Desať otázok cez celú teóriu grafov — od pojmu a stupňov po Eulerove ťahy.
Otestuj sa cez celú tému.