Síkdiagram:
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.
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 1 ,r 2 ,r 3 ,r 4 ,r 5 .
A gráfban négy véges régió található, azaz r 2 ,r 3 ,r 4 ,r 5 .
Egyetlen véges régió van, azaz r 1
A síkgrafikonok tulajdonságai:
- Ha egy G összefüggő síkgráfnak e éle és r területe van, akkor r ≦
Ez. - Ha egy G összefüggő síkgráfnak e éle, v csúcsa és r területe van, akkor v-e+r=2.
- Ha egy G összefüggő síkgráfnak e éle és v csúcsa van, akkor 3v-e≧6.
- Egy teljes gráf K n akkor és csak akkor sík, ha n <5. < li>
- Egy teljes kétrészes gráf K mn akkor és csak akkor sík, ha m3.
Példa: Bizonyítsuk be, hogy K teljes gráf 4 síkbeli.
Megoldás: A teljes gráf K 4 4 csúcsot és 6 élt tartalmaz.
Tudjuk, hogy összefüggő síkgráf esetén 3v-e≧6.Így K-re 4 , van 3x4-6=6, ami kielégíti a (3) tulajdonságot.
Így K 4 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 5 vagy K 3.3
1. példa: Mutasd meg, hogy K 5 nem síkbeli.
Megoldás: A teljes gráf K 5 5 csúcsot és 10 élt tartalmaz.
Most egy összefüggő síkgráfhoz 3v-e≧6.
Ezért K 5 , 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 5 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 5 vagy K 3.3 .
Megoldás: Ha eltávolítjuk a széleket (V 1 ,BAN BEN 4 ),(BAN BEN 3 ,BAN BEN 4 ) és (V 5 ,BAN BEN 4 ) a G grafikon 1 , homeomorf lesz K számára 5 .Ezért nem sík.
Ha eltávolítjuk az V élét 2,V 7) a G grafikon 2 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.
Példa: A K kromatikus száma n az n.
Megoldás: K színezése n n 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∈V deg(v)=2e
Bizonyíték: Legyen G = (V, E) egy gráf, ahol V = {v 1 ,ban ben 2 , . . . . . . . . . .} a csúcsok halmaza és E = {e 1 ,Ez 2 . . . . . . . . . .} 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∈V deg(v)=2e
