Egy gráfot síknak nevezünk, ha egy síkban úgy rajzolható meg, hogy nem keresztezi élét.

Példa: ábrán látható grafikon síkgrafikon.

bfa és b fa

Egy grafikon régiója: Tekintsünk egy G=(V,E) síkgráfot. A régió a sík élekkel határolt, tovább nem osztható területe. Egy síkgrafikon a terveket egy vagy több régióra osztja. E régiók egyike végtelen lesz.

Véges régió: Ha a tartomány területe véges, akkor ezt a tartományt véges tartománynak nevezzük.

Végtelen régió: Ha a terület területe végtelen, akkor ezt a tartományt végtelen tartománynak nevezzük. Egy síkgráfnak csak egy végtelen tartománya van.

Példa: Tekintsük az ábrán látható grafikont. Határozzuk meg a régiók, a véges régiók és a végtelen régiók számát!

Megoldás: A fenti grafikonon öt régió található, azaz r₁,r₂,r₃,r₄,r₅.

A gráfban négy véges régió található, azaz r₂,r₃,r₄,r₅.

Egyetlen véges régió van, azaz r₁

A síkgrafikonok tulajdonságai:

1. Ha egy G összefüggő síkgráfnak e éle és r területe van, akkor r ≦ Ez.
2. Ha egy G összefüggő síkgráfnak e éle, v csúcsa és r területe van, akkor v-e+r=2.
3. Ha egy G összefüggő síkgráfnak e éle és v csúcsa van, akkor 3v-e≧6.
4. Egy teljes gráf K_nakkor és csak akkor sík, ha n<5.< li>
5. Egy teljes kétrészes gráf K_mnakkor és csak akkor sík, ha m3.

Példa: Bizonyítsuk be, hogy K teljes gráf₄síkbeli.

Megoldás: A teljes gráf K₄4 csúcsot és 6 élt tartalmaz.

Tudjuk, hogy összefüggő síkgráf esetén 3v-e≧6.Így K-re₄, van 3x4-6=6, ami kielégíti a (3) tulajdonságot.

gépirat mindegyikhez

Így K₄egy sík gráf. Ezért bizonyított.

Nem síkbeli grafikon:

Egy gráfot nem síkbelinek mondunk, ha nem lehet síkban úgy megrajzolni, hogy éle ne keresztezzen.

Példa: ábrán látható grafikonok nem síkbeli gráfok.

Ezeket a gráfokat nem lehet síkban úgy megrajzolni, hogy egyetlen él se keresztezze egymást, ezért ezek nem síkbeli gráfok.

A nem síkbeli grafikonok tulajdonságai:

Egy gráf akkor és csak akkor nem síkbeli, ha K-vel homeomorf részgráfot tartalmaz₅vagy K_3.3

for ciklus java-ban

1. példa: Mutasd meg, hogy K₅nem síkbeli.

Megoldás: A teljes gráf K₅5 csúcsot és 10 élt tartalmaz.

Most egy összefüggő síkgráfhoz 3v-e≧6.

Ezért K₅, akkor 3 x 5-10=5 (ami nem felel meg a 3. tulajdonságnak, mert nagyobbnak vagy egyenlőnek kell lennie 6-nál).

Így K₅egy nem síkbeli gráf.

2. példa: Mutassuk meg, hogy az ábrán látható gráfok nem síkbeliek, keressünk egy K-vel homeomorf részgráfot₅vagy K_3.3.

Megoldás: Ha eltávolítjuk a széleket (V₁,BAN BEN₄),(BAN BEN₃,BAN BEN₄) és (V₅,BAN BEN₄) a G grafikon₁, homeomorf lesz K számára₅.Ezért nem sík.

Ha eltávolítjuk az V élét_2,V7) a G grafikon₂homeomorf lesz K-vel szemben_3.3.Ennélfogva ez egy nem sík.

Grafikon színezése:

Tegyük fel, hogy G= (V,E) olyan gráf, amelynek nincs több éle. A G csúcsszínezése színek hozzárendelése G csúcsaihoz úgy, hogy a szomszédos csúcsok különböző színűek. Egy G gráf M-színezhető, ha létezik G-nek olyan színezése, amely M-színeket használ.

Megfelelő színezés: A színezés akkor megfelelő, ha bármely két szomszédos u és v csúcs eltérő színű, különben nem megfelelő színezésnek nevezzük.

Példa: Tekintsük a következő grafikont és színt C={r, w, b, y}. Színezd ki a grafikont megfelelően az összes szín vagy kevesebb szín használatával.

ábrán látható grafikon minimum 3 színezhető, ezért x(G)=3

Megoldás: ábra mutatja a grafikont megfelelően színezve mind a négy színnel.

ábra mutatja a grafikont megfelelően színezve három színnel.

G kromatikus száma: A G gráf megfelelő színezéséhez szükséges minimális színszámot G kromatikus számának nevezzük, és x(G)-vel jelöljük.

mennyit nyom a kat timpf

Példa: A K kromatikus száma_naz n.

Megoldás: K színezése_nn szín felhasználásával szerkeszthető meg úgy, hogy minden csúcshoz más-más színt rendelünk. Nem lehet két csúcshoz azonos színt rendelni, mivel ennek a gráfnak minden két csúcsa szomszédos. Innen származik a K kromatikus száma_n=n.

Grafikonszínezés alkalmazásai

A grafikonszínezés néhány alkalmazása a következőket tartalmazza:

• Regisztrálás kiosztása
• Térkép színezése
• Bipartite Graph Checking
• Mobil rádiófrekvencia hozzárendelés
• Órarend készítés stb.

Mondja ki és bizonyítja a Kézfogás tételét!

Kézfogás tétel: A G gráf összes csúcsának fokösszege megegyezik a gráf éleinek kétszeresével.

Matematikailag így fogalmazható meg:

∑_v∈Vdeg(v)=2e

Bizonyíték: Legyen G = (V, E) egy gráf, ahol V = {v₁,ban ben₂, . . . . . . . . . .} a csúcsok halmaza és E = {e₁,Ez₂. . . . . . . . . .} az élek halmaza. Tudjuk, hogy minden él két csúcs között van, így minden csúcsnak első fokot ad. Ezért minden él a második fokozattal járul hozzá a gráfhoz. Tehát az összes csúcs fokszámának összege egyenlő a G éleinek kétszeresével.

Ezért ∑_v∈Vdeg(v)=2e

java összefűzött karakterláncok