Es diu que un gràfic és pla si es pot dibuixar en un pla de manera que cap aresta es creua.
Exemple: El gràfic que es mostra a la figura és un gràfic pla.
l'actor ranbir kapoor edat
Regió d'un gràfic: Considereu un gràfic pla G=(V,E). Una regió es defineix com una àrea del pla que està limitada per arestes i no es pot subdividir més. Un gràfic pla divideix els plans en una o més regions. Una d'aquestes regions serà infinita.
Regió finita: Si l'àrea de la regió és finita, aquesta regió s'anomena regió finita.
Regió infinita: Si l'àrea de la regió és infinita, aquesta regió s'anomena regió infinita. Un graf pla només té una regió infinita.
Exemple: Considereu el gràfic que es mostra a la figura. Determineu el nombre de regions, regions finites i una regió infinita.
Solució: Hi ha cinc regions al gràfic anterior, és a dir, r1,r2,r3,r4,r5.
Hi ha quatre regions finites al gràfic, és a dir, r2,r3,r4,r5.
Només hi ha una regió finita, és a dir, r1
Propietats dels gràfics planars:
- Si un graf pla connectat G té e arestes i r regions, aleshores r ≦
És. - Si un graf pla connectat G té e arestes, v vèrtexs i r regions, aleshores v-e+r=2.
- Si un graf pla connectat G té e arestes i v vèrtexs, aleshores 3v-e≧6.
- Un gràfic complet Knés un pla si i només si n<5.< li>
- Un gràfic bipartit complet Kmnés plana si i només si m3.
Exemple: Demostreu que la gràfica completa K4és plana.
Solució: El gràfic complet K4conté 4 vèrtexs i 6 arestes.
Sabem que per a un graf pla connectat 3v-e≧6. Per tant, per a K4, tenim 3x4-6=6 que compleix la propietat (3).
java invertint una cadena
Així K4és un gràfic pla. Per tant, demostrat.
Gràfic no planar:
Es diu que un gràfic no és pla si no es pot dibuixar en un pla de manera que cap aresta es creua.
Exemple: Els gràfics que es mostren a la figura són gràfics no plans.
Aquests gràfics no es poden dibuixar en un pla de manera que no es creuen arestes, per tant, són gràfics no plans.
Propietats dels gràfics no plans:
Un graf no és pla si i només si conté un subgraf homeomorf a K5o K3,3
declaració de cas java
Exemple 1: Demostra que K5no és plana.
Solució: El gràfic complet K5conté 5 vèrtexs i 10 arestes.
Ara, per a un gràfic pla connectat 3v-e≧6.
Per tant, per a K5, tenim 3 x 5-10=5 (que no compleix la propietat 3 perquè ha de ser major o igual a 6).
Així, K5és un gràfic no pla.
Exemple 2: Demostreu que els gràfics que es mostren a la figura no són planars trobant un subgraf homeomorf a K5o K3,3.
Solució: Si traiem les vores (V1, EN4),(IN3, EN4) i (V5, EN4) el gràfic G1, esdevé homeomorf a K5.Per tant, no és plana.
Si eliminem la vora V2,V7) el gràfic G2esdevé homeomorf a K3,3.Per tant, és un no pla.
Coloració del gràfic:
Suposem que G= (V,E) és un gràfic sense múltiples arestes. Una coloració de vèrtex de G és una assignació de colors als vèrtexs de G de manera que els vèrtexs adjacents tinguin colors diferents. Un gràfic G és M-Colorable si existeix una coloració de G que utilitza M-Colors.
proves de rendiment
Coloració adequada: Una coloració és pròpia si dos vèrtexs adjacents u i v tenen colors diferents, en cas contrari s'anomena coloració inadequada.
Exemple: Considereu el gràfic següent i coloreu C={r, w, b, y}. Pinteu el gràfic correctament utilitzant tots els colors o menys.
El gràfic que es mostra a la figura és un mínim de 3 colors, per tant, x(G)=3
Solució: La figura mostra el gràfic correctament acolorit amb els quatre colors.
La figura mostra el gràfic correctament acolorit amb tres colors.
Nombre cromàtic de G: El nombre mínim de colors necessaris per produir una coloració adequada d'un gràfic G s'anomena nombre cromàtic de G i es denota amb x(G).
Exemple: El nombre cromàtic de Knés n.
Solució: Un color de Knes pot construir utilitzant n colors assignant colors diferents a cada vèrtex. No es poden assignar dos vèrtexs amb els mateixos colors, ja que cada dos vèrtexs d'aquest gràfic són adjacents. D'aquí el nombre cromàtic de Kn=n.
Aplicacions de la coloració de gràfics
Algunes aplicacions de la coloració de gràfics inclouen:
- Registre d'assignació
- Mapa per pintar
- Comprovació de gràfics bipartits
- Assignació de freqüència de ràdio mòbil
- Elaboració d'un horari, etc.
Enuncia i demostra el teorema de l'encaixada.
Teorema de l'encaixada: La suma de graus de tots els vèrtexs d'un gràfic G és igual al doble del nombre d'arestes del gràfic.
Matemàticament es pot afirmar com:
∑v∈Vgrau(v)=2e
Prova: Sigui G = (V, E) un gràfic on V = {v1,en2, . . . . . . . . . .} sigui el conjunt de vèrtexs i E = {e1,És2. . . . . . . . . .} ser el conjunt d'arestes. Sabem que cada aresta es troba entre dos vèrtexs, de manera que proporciona un grau a cada vèrtex. Per tant, cada aresta aporta el grau dos per al gràfic. Per tant, la suma de graus de tots els vèrtexs és igual al doble del nombre d'arestes de G.
Per tant, ∑v∈Vgrau(v)=2e
q3 mesos