Rovinný graf:
O grafu se říká, že je rovinný, pokud jej lze nakreslit v rovině tak, že se žádná hrana nekříží.
Příklad: Graf zobrazený na obr je rovinný graf.
Oblast grafu: Uvažujme rovinný graf G=(V,E). Oblast je definována jako oblast roviny, která je ohraničena hranami a nelze ji dále dělit. Rovinný graf rozděluje plány do jedné nebo více oblastí. Jedna z těchto oblastí bude nekonečná.
Konečná oblast: Pokud je oblast oblasti konečná, pak se tato oblast nazývá konečná oblast.
Nekonečná oblast: Pokud je oblast oblasti nekonečná, nazývá se tato oblast nekonečnou oblastí. Rovinný graf má pouze jednu nekonečnou oblast.
Příklad: Uvažujme graf zobrazený na obr Určete počet oblastí, konečných oblastí a nekonečnou oblast.
Řešení: Ve výše uvedeném grafu je pět regionů, tj 1 ,r 2 ,r 3 ,r 4 ,r 5 .
V grafu jsou čtyři konečné oblasti, tj. r 2 ,r 3 ,r 4 ,r 5 .
Existuje pouze jedna konečná oblast, tj. r 1
Vlastnosti rovinných grafů:
- Pokud má souvislý rovinný graf G e hran a r oblastí, pak r ≦
To je. - Pokud má souvislý rovinný graf G e hran, v vrcholů a r oblastí, pak v-e+r=2.
- Pokud má souvislý rovinný graf G e hran a v vrcholů, pak 3v-e≧6.
- Kompletní graf K n je rovinný právě tehdy, když n <5. < li>
- Kompletní bipartitní graf K mn je rovinný právě tehdy, když m3.
Příklad: Dokažte, že celý graf K 4 je rovinný.
Řešení: Kompletní graf K 4 obsahuje 4 vrcholy a 6 hran.
Víme, že pro souvislý rovinný graf 3v-e≧6. Pro K 4 , máme 3x4-6=6, což splňuje vlastnost (3).
Tak K 4 je rovinný graf. Proto Proved.
Nerovinný graf:
O grafu se říká, že je nerovinný, pokud jej nelze nakreslit v rovině tak, aby se žádná hrana neprotínala.
Příklad: Grafy zobrazené na obr jsou nerovinné grafy.
Tyto grafy nelze kreslit v rovině, aby se žádné hrany nekřížily, jedná se tedy o nerovinné grafy.
Vlastnosti nerovinných grafů:
Graf je nerovinný právě tehdy, když obsahuje podgraf homeomorfní ke K 5 nebo K 3.3
Příklad1: Ukažte, že K 5 je nerovinná.
Řešení: Kompletní graf K 5 obsahuje 5 vrcholů a 10 hran.
Nyní pro souvislý rovinný graf 3v-e≧6.
Proto pro K 5 , máme 3 x 5-10=5 (což nesplňuje vlastnost 3, protože musí být větší nebo rovna 6).
Tedy K 5 je nerovinný graf.
Příklad2: Ukažte, že grafy zobrazené na obr jsou nerovinné tím, že naleznete podgraf homeomorfní ke K 5 nebo K 3.3 .
Řešení: Pokud odstraníme okraje (V 1 ,V 4 ),(V 3 ,V 4 ) a (V 5 ,V 4 ) graf G 1 , stane se homeomorfním na K 5 .Proto je nerovinný.
Pokud odstraníme okraj V 2,V 7) graf G 2 se stává homeomorfní pro K 3.3 .Proto je nerovinný.
Barvení grafu:
Předpokládejme, že G= (V,E) je graf bez více hran. Barvení vrcholu G je přiřazení barev k vrcholům G tak, že sousední vrcholy mají různé barvy. Graf G je M-Colorable, pokud existuje zbarvení G, které používá M-Colors.
Správné zbarvení: Zbarvení je správné, pokud jakékoli dva sousední vrcholy uav mají různé barvy, jinak se nazývá nesprávné zbarvení.
Příklad: Zvažte následující graf a barvu C={r, w, b, y}. Vybarvěte graf správně pomocí všech barev nebo méně barev.
Graf zobrazený na obr. je minimálně 3-barevný, proto x(G)=3
Řešení: Obrázek ukazuje graf správně vybarvený všemi čtyřmi barvami.
Obr ukazuje graf správně vybarvený třemi barvami.
Chromatické číslo G: Minimální počet barev potřebný k vytvoření správného vybarvení grafu G se nazývá chromatické číslo G a označuje se x(G).
Příklad: chromatické číslo K n je n.
Řešení: Zbarvení K n lze konstruovat pomocí n barev přiřazením různých barev každému vrcholu. Žádné dva vrcholy nemohou mít stejné barvy, protože každé dva vrcholy tohoto grafu sousedí. Odtud chromatické číslo K n =n.
Aplikace barvení grafů
Některé aplikace barvení grafů zahrnují:
- Registrovat přidělení
- Zbarvení mapy
- Kontrola bipartitního grafu
- Přidělování mobilních rádiových frekvencí
- Sestavení jízdního řádu atd.
Uveďte a dokažte větu o podání ruky.
Věta o podání ruky: Součet stupňů všech vrcholů v grafu G je roven dvojnásobku počtu hran v grafu.
Matematicky to lze říci takto:
∑ v∈V stupeň(v)=2e
Důkaz: Nechť G = (V, E) je graf, kde V = {v 1 ,v 2 , . . . . . . . . . .} je množina vrcholů a E = {e 1 ,To je 2 . . . . . . . . . .} být množina hran. Víme, že každá hrana leží mezi dvěma vrcholy, takže každému vrcholu poskytuje stupeň jedna. Každá hrana tedy přispívá ke druhému stupni grafu. Součet stupňů všech vrcholů je tedy roven dvojnásobku počtu hran v G.
Proto, ∑ v∈V stupeň(v)=2e
