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.
javascript ispis
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. r1,r2,r3,r4,r5.
Postoje četiri konačna područja u grafu, tj. r2,r3,r4,r5.
Postoji samo jedno konačno područje, tj. r1
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 Knje planarna ako i samo ako je n<5.< li>
- Kompletan bipartitni graf Kmnje planaran ako i samo ako je m3.
Primjer: Dokažite da je potpuni graf K4je ravninski.
Riješenje: Potpuni graf K4sadrži 4 vrha i 6 bridova.
Znamo da je za povezani ravninski graf 3v-e≧6. Stoga za K4, imamo 3x4-6=6 što zadovoljava svojstvo (3).
1 do 100 rimski br
Tako je K4je 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 K5ili K3.3
popis religija
Primjer1: Pokažite da je K5je neplanarna.
Riješenje: Potpuni graf K5sadrži 5 vrhova i 10 bridova.
Sada, za povezani planarni graf 3v-e≧6.
Dakle, za K5, imamo 3 x 5-10=5 (što ne zadovoljava svojstvo 3 jer mora biti veće ili jednako 6).
Dakle, K5je neplanaran graf.
Primjer2: Pokažite da su grafovi prikazani na sl. neplanarni pronalaskom podgrafa homeomorfnog K5ili K3.3.
Riješenje: Ako uklonimo rubove (V1,U4),(U3,U4) i (V5,U4) graf G1, postaje homeomorfan s K5.Stoga je neplanarna.
Ako uklonimo rub V2,V7) graf G2postaje homeomorfan K3.3.Stoga je neravninski.
java lista prazna
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 Knje n.
Riješenje: Boja Knmož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 Kn=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∈Vdeg(v)=2e
Dokaz: Neka je G = (V, E) graf gdje je V = {v1,u2, . . . . . . . . . .} biti skup vrhova i E = {e1,To je2. . . . . . . . . .} 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∈Vdeg(v)=2e
f filmovi