Graf je ravninski, če ga lahko narišemo v ravnini tako, da noben rob ne prečka.
primer: Graf, prikazan na sliki, je ravninski graf.
json v primeru json
Območje grafa: Razmislite o ravninskem grafu G=(V,E). Regija je definirana kot območje ravnine, ki je omejeno z robovi in ga ni mogoče nadalje razdeliti. Planarni graf razdeli načrte na eno ali več regij. Ena od teh regij bo neskončna.
Končna regija: Če je območje območja končno, se to območje imenuje končno območje.
Neskončno območje: Če je površina regije neskončna, se ta regija imenuje neskončna regija. Planarni graf ima samo eno neskončno regijo.
primer: Razmislite o grafu, prikazanem na sliki. Določite število regij, končnih regij in neskončne regije.
rešitev: V zgornjem grafu je pet regij, tj1,r2,r3,r4,r5.
V grafu so štiri končne regije, tj. r2,r3,r4,r5.
Obstaja samo ena končna regija, to je r1
Lastnosti ravninskih grafov:
- Če ima povezan ravninski graf G e robov in r regij, potem je r ≦
Je. - Če ima povezan ravninski graf G e robov, v oglišč in r regij, potem je v-e+r=2.
- Če ima povezan ravninski graf G e robov in v oglišč, potem velja 3v-e≧6.
- Celoten graf Knje ravnina, če in samo če je n<5.< li>
- Popolni bipartitni graf Kmnje ravninska, če in samo, če je m3.
primer: Dokažite, da popoln graf K4je planaren.
rešitev: Celoten graf K4vsebuje 4 oglišča in 6 robov.
Vemo, da za povezan ravninski graf velja 3v-e≧6. Zato za K4, imamo 3x4-6=6, kar zadošča lastnosti (3).
komisija za izbor kadrov pomen
Tako je K4je ravninski graf. Zato dokazano.
Neplanarni graf:
Za graf pravimo, da ni ravninski, če ga ni mogoče narisati v ravnino, tako da noben rob ne prečka.
primer: Grafi, prikazani na sliki, so neplanarni grafi.
Teh grafov ni mogoče narisati v ravnini, tako da se robovi ne sekajo, zato so neplanarni grafi.
Lastnosti neplanarnih grafov:
Graf je neplanaren, če in samo če vsebuje podgraf, homeomorfen K5ali K3.3
abeceda v številko
Primer1: Pokaži, da je K5je neplanarna.
rešitev: Celoten graf K5vsebuje 5 oglišč in 10 robov.
Zdaj pa za povezani ravninski graf 3v-e≧6.
Zato je za K5, imamo 3 x 5-10=5 (kar ne izpolnjuje lastnosti 3, ker mora biti večje ali enako 6).
Tako je K5je neplanaren graf.
Primer2: Dokažite, da so grafi, prikazani na sliki, neplanarni, tako da poiščete podgraf, homeomorfen K5ali K3.3.
rešitev: Če odstranimo robove (V1,IN4),(IN3,IN4) in (V5,IN4) graf G1, postane homeomorfen s K5.Zato je neplanarna.
Če odstranimo rob V2,V7) graf G2postane homeomorfen K3.3.Zato je neravninski.
Barvanje grafa:
Recimo, da je G= (V,E) graf brez več robov. Barvanje vozlišč G je dodelitev barv vozliščem G, tako da imajo sosednja vozlišča različne barve. Graf G je M-obarvan, če obstaja barvanje G, ki uporablja M-barve.
Pravilno barvanje: Barvanje je pravilno, če imata kateri koli dve sosednji vozlišči u in v različni barvi, sicer se imenuje nepravilno barvanje.
primer: Razmislite o naslednjem grafu in pobarvajte C={r, w, b, y}. Graf pravilno pobarvajte z vsemi ali manj barvami.
pretvori niz v objekt json
Graf, prikazan na sliki, je najmanj 3-barven, zato je x(G)=3
rešitev: Slika prikazuje pravilno obarvan graf z vsemi štirimi barvami.
Slika prikazuje graf, pravilno obarvan s tremi barvami.
Kromatsko število G: Najmanjše število barv, potrebnih za pravilno barvanje grafa G, se imenuje kromatsko število G in je označeno z x(G).
primer: Kromatsko število Knje n.
rešitev: Barva Knlahko sestavite z uporabo n barv tako, da vsakemu vozlišču dodelite različne barve. Dvema vozliščema ni mogoče dodeliti enakih barv, saj sta vsaki dve točki tega grafa sosednji. Od tod kromatsko število Kn=n.
Uporaba barvanja grafov
Nekatere aplikacije barvanja grafov vključujejo:
- Registracija Dodelitev
- Barvanje zemljevida
- Preverjanje bipartitnega grafa
- Dodelitev mobilne radijske frekvence
- Izdelava urnika itd.
Navedite in dokažite izrek rokovanja.
Izrek o rokovanju: Vsota stopinj vseh vozlišč v grafu G je enaka dvakratnemu številu robov v grafu.
Matematično se lahko izrazi kot:
∑v∈Vdeg(v)=2e
Dokaz: Naj bo G = (V, E) graf, kjer je V = {v1,v2, . . . . . . . . . .} je množica vozlišč in E = {e1,Je2. . . . . . . . . .} je množica robov. Vemo, da vsak rob leži med dvema vozliščema, tako da vsakemu vozlišču zagotavlja stopnjo ena. Zato vsak rob prispeva dve stopnji za graf. Torej je vsota stopinj vseh oglišč enaka dvakratnemu številu robov v G.
Torej, ∑v∈Vdeg(v)=2e
q3 mesece