Planarni grafikon:
Kaže se da je graf planaran ako se može nacrtati u ravnini tako da nijedan rub ne siječe.
Primjer: Graf prikazan na sl. je planarni graf.
Regija grafikona: Razmotrimo planarni graf G=(V,E). Regija je definirana kao područje ravnine koje je ograničeno rubovima i ne može se dalje dijeliti. Planarni graf dijeli planove u jednu ili više regija. Jedna od tih regija bit će beskonačna.
Konačna regija: Ako je površina regije konačna, tada se ta regija naziva konačnom regijom.
Beskonačno područje: Ako je površina regije beskonačna, ta regija se naziva beskonačna regija. Planarni graf ima samo jedno beskonačno područje.
Primjer: Razmotrite graf prikazan na slici. Odredite broj regija, konačnih regija i beskonačne regije.
Riješenje: Na gornjem grafikonu postoji pet regija, tj. r 1 ,r 2 ,r 3 ,r 4 ,r 5 .
Postoje četiri konačna područja u grafu, tj. r 2 ,r 3 ,r 4 ,r 5 .
Postoji samo jedno konačno područje, tj. r 1
Svojstva planarnih grafova:
- Ako povezani planarni graf G ima e bridova i r područja, tada je r ≦
To je. - Ako povezani planarni graf G ima e bridova, v vrhova i r područja, tada je v-e+r=2.
- Ako povezani planarni graf G ima e bridova i v vrhova, tada je 3v-e≧6.
- Kompletan graf K n je planarna ako i samo ako je n <5. < li>
- Kompletan bipartitni graf K mn je planaran ako i samo ako je m3.
Primjer: Dokažite da je potpuni graf K 4 je ravninski.
Riješenje: Potpuni graf K 4 sadrži 4 vrha i 6 bridova.
Znamo da je za povezani ravninski graf 3v-e≧6. Stoga za K 4 , imamo 3x4-6=6 što zadovoljava svojstvo (3).
Tako je K 4 je planarni graf. Stoga je dokazano.
Neplanarni grafikon:
Za graf se kaže da nije planaran ako se ne može nacrtati u ravnini tako da nema križanja rubova.
Primjer: Grafikoni prikazani na sl. su neplanarni grafovi.
Ti se grafovi ne mogu nacrtati u ravnini tako da se rubovi ne križaju, stoga su oni neplanarni grafovi.
Svojstva neplanarnih grafova:
Graf je neplanaran ako i samo ako sadrži podgraf homeomorfan K 5 ili K 3.3
Primjer1: Pokažite da je K 5 je neplanarna.
Riješenje: Potpuni graf K 5 sadrži 5 vrhova i 10 bridova.
Sada, za povezani planarni graf 3v-e≧6.
Dakle, za K 5 , imamo 3 x 5-10=5 (što ne zadovoljava svojstvo 3 jer mora biti veće ili jednako 6).
Dakle, K 5 je neplanaran graf.
Primjer2: Pokažite da su grafovi prikazani na sl. neplanarni pronalaskom podgrafa homeomorfnog K 5 ili K 3.3 .
Riješenje: Ako uklonimo rubove (V 1 ,U 4 ),(U 3 ,U 4 ) i (V 5 ,U 4 ) graf G 1 , postaje homeomorfan s K 5 .Stoga je neplanarna.
Ako uklonimo rub V 2,V 7) graf G 2 postaje homeomorfan K 3.3 .Stoga je neravninski.
Bojanje grafikona:
Pretpostavimo da je G= (V,E) graf bez više bridova. Bojanje vrhova G je dodjeljivanje boja vrhovima G tako da susjedni vrhovi imaju različite boje. Graf G je M-obojiv ako postoji bojanje G koje koristi M-boje.
Pravilno bojanje: Bojanje je ispravno ako bilo koja dva susjedna vrha u i v imaju različite boje, inače se naziva nepravilnim bojanjem.
Primjer: Razmotrite sljedeći grafikon i obojite ga C={r, w, b, y}. Obojite grafikon pravilno koristeći sve boje ili manji broj boja.
Graf prikazan na slici je minimalno 3-bojljiv, stoga je x(G)=3
Riješenje: Slika prikazuje grafikon pravilno obojen sa sve četiri boje.
Slika prikazuje grafikon ispravno obojen s tri boje.
Kromatski broj G: Najmanji broj boja potrebnih za pravilno bojanje grafa G naziva se kromatskim brojem G i označava se s x(G).
Primjer: Kromatski broj K n je n.
Riješenje: Boja K n može se konstruirati pomoću n boja dodjeljivanjem različitih boja svakom vrhu. Dva vrha ne mogu biti dodijeljene iste boje, jer su svaka dva vrha ovog grafa susjedna. Otuda kromatski broj K n =n.
Primjene bojanja grafikona
Neke primjene bojanja grafikona uključuju:
- Registrirajte dodjelu
- Bojanje karte
- Provjera bipartitnog grafa
- Dodjela mobilne radiofrekvencije
- Izrada satnice i sl.
Navedite i dokažite teorem o rukovanju.
Teorem o rukovanju: Zbroj stupnjeva svih vrhova u grafu G jednak je dvostrukom broju bridova u grafu.
Matematički se to može izraziti kao:
∑ v∈V deg(v)=2e
Dokaz: Neka je G = (V, E) graf gdje je V = {v 1 ,u 2 , . . . . . . . . . .} biti skup vrhova i E = {e 1 ,To je 2 . . . . . . . . . .} biti skup bridova. Znamo da svaki brid leži između dva vrha tako da daje stupanj jedan svakom vrhu. Stoga svaki brid doprinosi stupnju dva za graf. Dakle, zbroj stupnjeva svih vrhova jednak je dvostrukom broju bridova u G.
Dakle, ∑ v∈V deg(v)=2e
