Plan graf:
En graf siges at være plan, hvis den kan tegnes i et plan, så ingen kant krydser.
Eksempel: Grafen vist i fig. er plan graf.
Region af en graf: Betragt en plan graf G=(V,E). Et område er defineret som et område af planet, der er afgrænset af kanter og ikke kan underinddeles yderligere. En plan graf opdeler planerne i en eller flere regioner. En af disse regioner vil være uendelig.
Finite Region: Hvis området i området er begrænset, kaldes det område for et begrænset område.
Uendelig region: Hvis området i området er uendeligt, kaldes det et uendeligt område. En plan graf har kun et uendeligt område.
Eksempel: Overvej grafen vist i fig. Bestem antallet af områder, endelige områder og et uendeligt område.
Løsning: Der er fem regioner i ovenstående graf, dvs 1 ,r 2 ,r 3 ,r 4 ,r 5 .
Der er fire endelige områder i grafen, dvs. r 2 ,r 3 ,r 4 ,r 5 .
Der er kun én endelig region, dvs. r 1
Egenskaber for plane grafer:
- Hvis en forbundet plan graf G har e kanter og r områder, så er r ≦
Det er. - Hvis en forbundet plan graf G har e kanter, v hjørner og r områder, så er v-e+r=2.
- Hvis en forbundet plan graf G har e kanter og v spidser, så 3v-e≧6.
- En komplet graf K n er en plan hvis og kun hvis n <5. < li>
- En komplet todelt graf K mn er plan hvis og kun hvis m3.
Eksempel: Bevis den komplette graf K 4 er plan.
Løsning: Den komplette graf K 4 indeholder 4 hjørner og 6 kanter.
Vi ved, at for en forbundet plan graf 3v-e≧6. Derfor for K 4 , vi har 3x4-6=6 som opfylder ejendommen (3).
Således K 4 er en plan graf. Derfor bevist.
Ikke-planart graf:
En graf siges at være ikke-plan, hvis den ikke kan tegnes i et plan, så ingen kant krydser.
Eksempel: Graferne vist i fig. er ikke-plane grafer.
Disse grafer kan ikke tegnes i et plan, så ingen kanter krydser, derfor er de ikke-plane grafer.
Egenskaber for ikke-planære grafer:
En graf er ikke-plan, hvis og kun hvis den indeholder en subgraf, der er homøomorf til K 5 eller K 3.3
Eksempel 1: Vis at K 5 er ikke-plan.
Løsning: Den komplette graf K 5 indeholder 5 hjørner og 10 kanter.
Nu, for en forbundet plan graf 3v-e≧6.
Derfor for K 5 , vi har 3 x 5-10=5 (som ikke opfylder egenskab 3, fordi den skal være større end eller lig med 6).
Således K 5 er en ikke-plan graf.
Eksempel 2: Vis, at graferne vist i fig er ikke-plane ved at finde en subgraf, der er homøomorf til K 5 eller K 3.3 .
Løsning: Hvis vi fjerner kanterne (V 1 ,I 4 ),(I 3 ,I 4 ) og (V 5 ,I 4 ) grafen G 1 , bliver homøomorf til K 5 .Derfor er den ikke-plan.
Hvis vi fjerner kanten V 2,V 7) grafen G 2 bliver homøomorf for K 3.3 .Derfor er det en ikke-plan.
Graffarvning:
Antag, at G= (V,E) er en graf uden flere kanter. En toppunktfarvning af G er en tildeling af farver til toppunkterne på G, således at tilstødende toppunkter har forskellige farver. En graf G er M-farverbar, hvis der findes en farve af G, som bruger M-farver.
Korrekt farve: En farve er korrekt, hvis to tilstødende hjørner u og v har forskellige farver ellers kaldes det forkert farve.
Eksempel: Overvej følgende graf og farve C={r, w, b, y}. Farv grafen korrekt med alle farver eller færre farver.
Grafen vist i fig er mindst 3-farverbar, derfor x(G)=3
Løsning: Fig. viser grafen korrekt farvet med alle fire farver.
Fig. viser grafen korrekt farvet med tre farver.
Kromatisk antal G: Det mindste antal farver, der er nødvendige for at producere en korrekt farvning af en graf G, kaldes det kromatiske antal G og er angivet med x(G).
Eksempel: Det kromatiske antal K n er n.
Løsning: En farve af K n kan konstrueres ved hjælp af n farver ved at tildele forskellige farver til hvert toppunkt. Ikke to hjørner kan tildeles de samme farver, da hver to hjørner af denne graf er tilstødende. Derfor det kromatiske antal K n =n.
Anvendelser af graffarvning
Nogle anvendelser af graffarvning inkluderer:
- Registertildeling
- Kort farvelægning
- Todelt grafkontrol
- Mobilradiofrekvenstildeling
- Udarbejdelse af tidsplan mv.
Angiv og bevis Handshaking Theorem.
Håndtrykssætning: Summen af grader af alle hjørnerne i en graf G er lig med det dobbelte af antallet af kanter i grafen.
Matematisk kan det siges som:
∑ v∈V grader(v)=2e
Bevis: Lad G = (V, E) være en graf, hvor V = {v 1 ,i 2 , . . . . . . . . . .} være mængden af toppunkter og E = {e 1 ,Det er 2 . . . . . . . . . .} være sæt af kanter. Vi ved, at hver kant ligger mellem to toppunkter, så det giver grad et til hvert toppunkt. Derfor bidrager hver kant med grad to for grafen. Så summen af grader af alle hjørner er lig med det dobbelte af antallet af kanter i G.
Derfor ∑ v∈V grader(v)=2e
