Speciální grafy
Proč to potřebuji?
Ne všechny grafy jsou si rovny. Některé mají speciální strukturu, která nám umožňuje řešit důležité praktické problémy -- od plánování tras (eulerovské a hamiltonovské grafy), přes návrh tištěných spojů (rovinné grafy), až po přiřazovací úlohy (bipartitní grafy). Znalost těchto tříd grafů a jejich vlastností je klíčová pro efektivní algoritmické řešení reálných problémů.
Předpoklady: Základní pojmy teorie grafů (vrcholy, hrany, stupně, souvislost) z Tématu 1.
Teorie
2.1 Bipartitní grafy
Bipartitní graf: graf, jehož množinu vrcholů můžeme rozdělit do dvou množin V1 a V2 tak, že:
- V1 ∩ V2 = ∅ a V1 ∪ V2 = V
- Každá hrana má jeden koncový vrchol ve V1 a druhý ve V2
Úplný bipartitní graf Kr,s: každý z r vrcholů V1 je spojen s každým z s vrcholů V2. Má r · s hran.
K3,2
K1,3
Graf G je bipartitní právě tehdy, když neobsahuje kružnici liché délky.
Začněte u libovolného vrcholu, dejte ho do skupiny 1 (červená). Všechny jeho sousedy dejte do skupiny 2 (modrá). Sousedy těch do skupiny 1 atd. Pokud se vám podaří rozdělit všechny bez konfliktu ⇒ bipartitní.
2.2 Hamiltonovské grafy
- Hamiltonovská kružnice: kružnice obsahující všechny vrcholy grafu
- Hamiltonovský graf: graf, ve kterém existuje hamiltonovská kružnice
Problém: problém cestujícího — navštívit každé město právě jednou.
- Hamiltonovská kružnice má právě n hran (pro n vrcholů)
- Přes každý vrchol procházejí právě 2 hrany hamiltonovky
- Nesmí vzniknout kružnice, která neobsahuje všechny vrcholy
- Jakmile hamiltonovka projde vrcholem v, ostatní hrany incidentní s v můžeme vyloučit
- Hamiltonovský graf neobsahuje most
- Hamiltonovský graf neobsahuje artikulaci
- Bipartitní graf s lichým počtem vrcholů není hamiltonovský
2.3 Eulerovské grafy
- Eulerovský tah: tah, který obsahuje všechny hrany grafu
- Eulerovský graf: souvislý graf, ve kterém existuje eulerovský tah
Problém: problém průzkumníka/pošťáka — projít každou ulicí právě jednou.
Graf G je eulerovský právě tehdy, když je souvislý a má buď:
- všechny vrcholy sudého stupně (uzavřený eulerovský tah), nebo
- právě dva vrcholy lichého stupně (otevřený eulerovský tah — začíná a končí v lichých vrcholech)
| Eulerovský | Hamiltonovský | |
|---|---|---|
| Co procházíme | Všechny HRANY | Všechny VRCHOLY |
| Podmínka | Souvislý + sudé stupně (nebo 2 liché) | Žádná jednoduchá podmínka |
| Analogie | Pošťák (všechny ulice) | Cestovatel (všechna města) |
2.4 Rovinné grafy
Rovinný graf: graf, který lze nakreslit v rovině bez křížení hran.
Pro souvislý rovinný graf platí:
kde F je množina stěn (oblastí) rovinného nakreslení.
- Pokud G je rovinný a |V| ≥ 3:
|E| ≤ 3|V| - 6 - Pokud G je rovinný, |V| ≥ 3 a neobsahuje K3 jako podgraf:
|E| ≤ 2|V| - 4 - Obměna: Pokud |E| > 3|V| - 6, pak graf není rovinný
K5 a K3,3 nejsou rovinné. Obsahuje-li graf K5 nebo K3,3 jako podgraf (či jejich dělení) ⇒ není rovinný.
2.5 Barevnost, klikovost, nezávislost
- Barevnost (chromatické číslo): minimální počet barev na obarvení vrcholů tak, aby sousední vrcholy měly různou barvu
- Klikovost: velikost největší kliky (kompletního podgrafu)
- Nezávislost: velikost nejpočetnější nezávislé množiny (žádné dva vrcholy nejsou sousední)
Cvičení
Cvičení 1: Má-li graf 4 liché vrcholy, je eulerovský? A co když má artikulaci -- může být hamiltonovský?
4 liché vrcholy → není eulerovský (musí být 0 nebo právě 2 liché)
Má artikulaci → není hamiltonovský (hamiltonovská kružnice nemá artikulaci)
Cvičení 2: Nakreslete grafy s danou vlastností:
a) Graf, který je eulerovský a zároveň hamiltonovský
b) Graf, který je eulerovský a není hamiltonovský
c) Graf, který není eulerovský a je hamiltonovský
a) EG + HG: např. K5 (všechny stupně = 4, sudé; obsahuje hamiltonovku)
b) EG, ne HG: dva trojúhelníky spojené jedním společným vrcholem (artikulace) -- všechny stupně sudé, ale má artikulaci
c) Ne EG, HG: např. kružnice C5 s jednou diagonálou -- má 4 liché vrcholy, ale hamiltonovka existuje
Cvičení 3: Může být graf se skóre (2,4,4,5,5,6,6,6) rovinný?
n = 8, m = (2+4+4+5+5+6+6+6)/2 = 38/2 = 19
Podmínka: |E| ≤ 3|V| - 6 ⇒ 19 ≤ 3·8 - 6 = 18?
19 > 18 ⇒ NE, není rovinný
Cvičení 4: 8 kamarádů chce posadit ke 2 stolům tak, aby u každého stolu seděli jen ti, kteří se neznají. Vztahy: a-d,f,g; b-c,d,h; c-b,e; d-a,b,f; e-c,f; f-a,d,e; g-a; h-b. Je to možné?
Jde o bipartitní graf. Rozdělíme do dvou skupin:
Začneme: a→1, d→2, f→2, g→2, b→1 (soused d), c→2 (soused b), h→2 (soused b), e→1 (soused c,f).
Ověření: d(2) a f(2) jsou oba ve skupině 2, ale jsou sousední ⇒ graf obsahuje lichou kružnici ⇒ není bipartitní, nelze rozdělit.
Cvičení 5: Vytvořte negaci a obměnu: ∀ G=(V,E): G je hamiltonovský ⇒ G neobsahuje artikulaci
Negace: ∃ G=(V,E): G je hamiltonovský ∧ G obsahuje artikulaci
Obměna: ∀ G=(V,E): G obsahuje artikulaci ⇒ G není hamiltonovský
Cvičení 6: Který graf je vždy eulerovský?
a) K5 (všechny stupně 4) b) K4 (všechny stupně 3) c) Cesta P4 d) Strom
a) K5 -- všechny stupně jsou 4 (sudé), graf je souvislý, tedy je eulerovský. K4 má stupně 3 (liché), cesta i strom mají vždy alespoň 2 liché vrcholy (listy).
Cvičení 7: Graf je bipartitní právě tehdy, když...
a) má sudý počet vrcholů b) neobsahuje kružnici liché délky c) všechny vrcholy mají sudý stupeň d) je rovinný
b) neobsahuje kružnici liché délky -- to je přesně charakterizace bipartitních grafů.
Shrnutí
Klíčové pojmy a vlastnosti
- Bipartitní graf: vrcholy lze rozdělit do dvou skupin, hrany vedou jen mezi skupinami; charakterizace: neobsahuje lichou kružnici
- Hamiltonovský graf: obsahuje kružnici přes všechny vrcholy; nemá most ani artikulaci
- Eulerovský graf: obsahuje tah přes všechny hrany; souvislý + všechny stupně sudé (nebo právě 2 liché)
- Rovinný graf: nakreslitelný bez křížení hran; Eulerova věta: |F| = |E| - |V| + 2
- Podmínka rovinnosti: |E| ≤ 3|V| - 6; K5 a K3,3 nejsou rovinné
- Barevnost: minimální počet barev pro obarvení vrcholů