logo

Planar graf:

En graf sies å være plan hvis den kan tegnes i et plan slik at ingen kantkryss.

Eksempel: Grafen vist i fig er plan graf.

kandidatnøkkel
Plane og ikke-planare grafer
Plane og ikke-planare grafer

Region av en graf: Betrakt en plan graf G=(V,E). Et område er definert til å være et område av planet som er avgrenset av kanter og ikke kan deles inn ytterligere. En plan graf deler planene inn i en eller flere regioner. En av disse regionene vil være uendelig.

Finitt region: Hvis området i regionen er begrenset, kalles den regionen en endelig region.

Uendelig region: Hvis området i regionen er uendelig, kalles den regionen en uendelig region. En plan graf har bare ett uendelig område.

Eksempel: Tenk på grafen vist i fig. Bestem antall regioner, endelige områder og en uendelig region.

Plane og ikke-planare grafer

Løsning: Det er fem regioner i grafen ovenfor, dvs. r1,r2,r3,r4,r5.

Det er fire endelige områder i grafen, dvs. r2,r3,r4,r5.

Det er bare ett begrenset område, dvs. r1

Egenskaper til plane grafer:

  1. Hvis en tilkoblet plan graf G har e kanter og r områder, så er r ≦ Plane og ikke-planare graferDet er.
  2. Hvis en tilkoblet plan graf G har e kanter, v toppunkter og r områder, så er v-e+r=2.
  3. Hvis en tilkoblet plan graf G har e kanter og v toppunkter, så 3v-e≧6.
  4. En komplett graf Kner en plan hvis og bare hvis n<5.< li>
  5. En komplett todelt graf Kmner plan hvis og bare hvis m3.

Eksempel: Bevis at fullstendig graf K4er plan.

Løsning: Den komplette grafen K4inneholder 4 hjørner og 6 kanter.

Vi vet at for en tilkoblet plan graf 3v-e≧6.Derav for K4, vi har 3x4-6=6 som tilfredsstiller egenskapen (3).

tuppel java

Dermed K4er en plan graf. Derfor bevist.

Ikke-planart graf:

En graf sies å være ikke-plan hvis den ikke kan tegnes i et plan slik at ingen kantkryss.

Eksempel: Grafene vist i fig er ikke-plane grafer.

Plane og ikke-planare grafer

Disse grafene kan ikke tegnes i et plan slik at ingen kanter krysser hverandre, derfor er de ikke-plane grafer.

Egenskaper til ikke-planære grafer:

En graf er ikke-plan hvis og bare hvis den inneholder en subgraf som er homeomorf til K5eller K3.3

inordergjennomgang

Eksempel 1: Vis at K5er ikke-plan.

Løsning: Den komplette grafen K5inneholder 5 hjørner og 10 kanter.

Nå, for en tilkoblet plan graf 3v-e≧6.

Derfor, for K5, vi har 3 x 5-10=5 (som ikke tilfredsstiller egenskap 3 fordi den må være større enn eller lik 6).

Dermed K5er en ikke-plan graf.

Eksempel 2: Vis at grafene vist i fig er ikke-plane ved å finne en subgraf som er homeomorf til K5eller K3.3.

Plane og ikke-planare grafer
Plane og ikke-planare grafer

Løsning: Hvis vi fjerner kantene (V1,I4),(I3,I4) og (V5,I4) grafen G1, blir homeomorf til K5.Derfor er den ikke-plan.

Hvis vi fjerner kanten V2,V7) grafen G2blir homeomorf for K3.3.Derfor er det en ikke-planar.

Graffarging:

Anta at G= (V,E) er en graf uten flere kanter. En toppunktfarging av G er en tilordning av farger til toppunktene til G slik at tilstøtende toppunkter har forskjellige farger. En graf G er M-fargebar hvis det finnes en fargelegging av G som bruker M-farger.

Riktig fargelegging: En fargelegging er riktig hvis to tilstøtende hjørner u og v har forskjellige farger ellers kalles det feilfarging.

Eksempel: Tenk på følgende graf og farge C={r, w, b, y}. Farg grafen riktig med alle farger eller færre farger.

Plane og ikke-planare grafer

Grafen vist i fig er minimum 3-fargerbar, derav x(G)=3

Løsning: Fig viser grafen riktig farget med alle de fire fargene.

Plane og ikke-planare grafer

Fig viser grafen riktig farget med tre farger.

Kromatisk antall G: Minimumsantallet av farger som trengs for å produsere en riktig fargelegging av en graf G kalles det kromatiske antallet G og er betegnet med x(G).

git pull origin master

Eksempel: Det kromatiske tallet til Kner n.

Løsning: En fargelegging av Knkan konstrueres ved å bruke n farger ved å tilordne forskjellige farger til hvert toppunkt. Ingen to toppunkter kan tildeles de samme fargene, siden hver to toppunkter i denne grafen er tilstøtende. Derav det kromatiske tallet til Kn=n.

Anvendelser av graffarging

Noen bruksområder for graffarging inkluderer:

  • Registrer Tildeling
  • Kartfarging
  • Todelt grafkontroll
  • Mobilradiofrekvenstilordning
  • Lage timeplan osv.

Angi og bevis Handshaking Theorem.

Handshaking Theorem: Summen av grader av alle toppunktene i en graf G er lik to ganger antall kanter i grafen.

Matematisk kan det si:

v∈Vgrader(v)=2e

Bevis: La G = (V, E) være en graf der V = {v1,i2, . . . . . . . . . .} være settet med toppunkter og E = {e1,Det er2. . . . . . . . . .} være settet med kanter. Vi vet at hver kant ligger mellom to toppunkter, så den gir grad én til hvert toppunkt. Derfor bidrar hver kant med grad to for grafen. Så summen av grader av alle hjørner er lik to ganger antall kanter i G.

Derfor, ∑v∈Vgrader(v)=2e

er modelleksempler