Rovinný graf:
O grafe sa hovorí, že je rovinný, ak sa dá nakresliť v rovine tak, že sa neprekrižuje žiadna hrana.
Príklad: Graf znázornený na obr je rovinný graf.
Oblasť grafu: Uvažujme rovinný graf G=(V,E). Oblasť je definovaná ako oblasť roviny, ktorá je ohraničená hranami a nemožno ju ďalej deliť. Rovinný graf rozdeľuje plány do jednej alebo viacerých oblastí. Jedna z týchto oblastí bude nekonečná.
Konečná oblasť: Ak je oblasť oblasti konečná, potom sa táto oblasť nazýva konečná oblasť.
Nekonečný región: Ak je oblasť oblasti nekonečná, táto oblasť sa nazýva nekonečná oblasť. Rovinný graf má iba jednu nekonečnú oblasť.
Príklad: Uvažujme o grafe na obr. Určte počet oblastí, konečných oblastí a nekonečnej oblasti.
Riešenie: Vo vyššie uvedenom grafe je päť regiónov, t.j 1 ,r 2 ,r 3 ,r 4 ,r 5 .
V grafe sú štyri konečné oblasti, t.j. r 2 ,r 3 ,r 4 ,r 5 .
Existuje len jedna konečná oblasť, t.j. r 1
Vlastnosti planárnych grafov:
- Ak má súvislý rovinný graf G e hrán a r oblastí, potom r ≦
To je. - Ak má súvislý rovinný graf G e hrán, v vrcholov a r oblastí, potom v-e+r=2.
- Ak má súvislý rovinný graf G e hrán a v vrcholov, potom 3v-e≧6.
- Kompletný graf K n je rovinný práve vtedy, ak n <5. < li>
- Kompletný bipartitný graf K mn je rovinný práve vtedy, ak m3.
Príklad: Dokážte, že celý graf K 4 je rovinný.
Riešenie: Kompletný graf K 4 obsahuje 4 vrcholy a 6 hrán.
Vieme, že pre súvislý rovinný graf 3v-e≧6. Preto pre K 4 , máme 3x4-6=6, čo spĺňa vlastnosť (3).
Takto K 4 je rovinný graf. Preto Dokázané.
Nerovinný graf:
O grafe sa hovorí, že je nerovinný, ak ho nemožno nakresliť v rovine tak, aby sa neprekrížila žiadna hrana.
Príklad: Grafy zobrazené na obr sú nerovinné grafy.
Tieto grafy nie je možné kresliť v rovine, aby sa neprekrížili žiadne hrany, preto ide o nerovinné grafy.
Vlastnosti nerovinných grafov:
Graf je nerovinný práve vtedy, ak obsahuje podgraf homeomorfný ku K 5 alebo K 3.3
Príklad1: Ukážte, že K 5 je nerovinná.
Riešenie: Kompletný graf K 5 obsahuje 5 vrcholov a 10 hrán.
Teraz pre spojený rovinný graf 3v-e≧6.
Preto pre K 5 , máme 3 x 5-10=5 (čo nespĺňa vlastnosť 3, pretože musí byť väčšia alebo rovná 6).
Preto K 5 je nerovinný graf.
Príklad2: Ukážte, že grafy zobrazené na obrázku sú nerovinné, nájdením podgrafu homeomorfného ku K 5 alebo K 3.3 .
Riešenie: Ak odstránime okraje (V 1 ,V 4 ),(V 3 ,V 4 ) a (V 5 ,V 4 ) graf G 1 , sa stáva homeomorfným ku K 5 .Preto je nerovinný.
Ak odstránime okraj V 2,V 7) graf G 2 sa stáva homeomorfným ku K 3.3 .Preto je nerovinný.
Farbenie grafu:
Predpokladajme, že G= (V,E) je graf bez viacerých hrán. Zafarbenie vrcholu G je priradenie farieb vrcholom G tak, že susedné vrcholy majú rôzne farby. Graf G je M-farebný, ak existuje sfarbenie G, ktoré používa M-farby.
Správne sfarbenie: Zafarbenie je správne, ak akékoľvek dva susedné vrcholy u a v majú rôzne farby, inak sa nazýva nesprávne sfarbenie.
Príklad: Zvážte nasledujúci graf a farbu C={r, w, b, y}. Vyfarbite graf správne použitím všetkých farieb alebo menej farieb.
Graf znázornený na obr je možné vyfarbiť minimálne tromi farbami, teda x(G)=3
Riešenie: Obrázok ukazuje graf správne vyfarbený všetkými štyrmi farbami.
Obr ukazuje graf správne vyfarbený tromi farbami.
Chromatické číslo G: Minimálny počet farieb potrebný na vytvorenie správneho sfarbenia grafu G sa nazýva chromatické číslo G a označuje sa x(G).
Príklad: Chromatické číslo K n je n.
Riešenie: Sfarbenie K n možno skonštruovať pomocou n farieb priradením rôznych farieb každému vrcholu. Žiadne dva vrcholy nemôžu mať priradené rovnaké farby, pretože každé dva vrcholy tohto grafu sú susediace. Preto chromatické číslo K n =n.
Aplikácie farbenia grafov
Niektoré aplikácie farbenia grafov zahŕňajú:
- Registrovať pridelenie
- Farbenie mapy
- Kontrola bipartitného grafu
- Mobilné rádiové pridelenie frekvencie
- Zostavenie časového harmonogramu atď.
Uveďte a dokážte vetu o podávaní rúk.
Veta o podávaní rúk: Súčet stupňov všetkých vrcholov v grafe G sa rovná dvojnásobku počtu hrán v grafe.
Matematicky to možno povedať takto:
∑ v∈V stupeň(v)=2e
dôkaz: Nech G = (V, E) je graf, kde V = {v 1 ,v 2 , . . . . . . . . . .} je množina vrcholov a E = {e 1 ,To je 2 . . . . . . . . . .} byť množina hrán. Vieme, že každá hrana leží medzi dvoma vrcholmi, takže každému vrcholu poskytuje stupeň jedna. Každá hrana teda prispieva ku stupňu dva pre graf. Súčet stupňov všetkých vrcholov sa teda rovná dvojnásobku počtu hrán v G.
Preto ∑ v∈V stupeň(v)=2e
