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, tj₁,r₂,r₃,r₄,r₅.

V grafu so štiri končne regije, tj. r₂,r₃,r₄,r₅.

Obstaja samo ena končna regija, to je r₁

Lastnosti ravninskih grafov:

1. Če ima povezan ravninski graf G e robov in r regij, potem je r ≦ Je.
2. Če ima povezan ravninski graf G e robov, v oglišč in r regij, potem je v-e+r=2.
3. Če ima povezan ravninski graf G e robov in v oglišč, potem velja 3v-e≧6.
4. Celoten graf K_nje ravnina, če in samo če je n<5.< li>
5. Popolni bipartitni graf K_mnje ravninska, če in samo, če je m3.

primer: Dokažite, da popoln graf K₄je planaren.

rešitev: Celoten graf K₄vsebuje 4 oglišča in 6 robov.

Vemo, da za povezan ravninski graf velja 3v-e≧6. Zato za K₄, imamo 3x4-6=6, kar zadošča lastnosti (3).

komisija za izbor kadrov pomen

Tako je K₄je 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 K₅ali K_3.3

abeceda v številko

Primer1: Pokaži, da je K₅je neplanarna.

rešitev: Celoten graf K₅vsebuje 5 oglišč in 10 robov.

Zdaj pa za povezani ravninski graf 3v-e≧6.

Zato je za K₅, imamo 3 x 5-10=5 (kar ne izpolnjuje lastnosti 3, ker mora biti večje ali enako 6).

Tako je K₅je neplanaren graf.

Primer2: Dokažite, da so grafi, prikazani na sliki, neplanarni, tako da poiščete podgraf, homeomorfen K₅ali K_3.3.

rešitev: Če odstranimo robove (V₁,IN₄),(IN₃,IN₄) in (V₅,IN₄) graf G₁, postane homeomorfen s K₅.Zato je neplanarna.

Če odstranimo rob V_2,V7) graf G₂postane homeomorfen K_3.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 K_nje n.

rešitev: Barva K_nlahko 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 K_n=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 = {v₁,v₂, . . . . . . . . . .} je množica vozlišč in E = {e₁,Je₂. . . . . . . . . .} 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