Graf pla

De Viquipèdia
Dreceres ràpides: navegació, cerca
Grafs d'exemple
Planar No planar
Graf planar
K 5
El graf complet K 4 és pla
K 3,3


En teoria de grafs, un graf pla (o planar) és un graf que pot ser dibuixat en el pla sense que cap aresta s'intersequi (una definició més formal pot ser que aquest graf pugui ser "embegut" en un pla). Un graf no és pla si no pot ser dibuixat sobre un pla sense que les seves arestes es intersequen. Els grafs K 5 i el K 3,3 són els grafs no plans minimals, la qual cosa ens permetran caracteritzar la resta dels grafs no plans.

Teorema de Kuratowski[modifica | modifica el codi]

El matemàtic polonès Kazimierz Kuratowski va trobar una caracterització dels grafs plans, coneguda com el teorema de Kuratowski :

Un graf és pla si i només si no conté un subgraf que és una subdivisió elemental de K 5 (el graf complet de 5 vèrtexs) o K 3,3 (el graf bipartit complet de 6 vèrtexs).

Una subdivisió elemental d'un graf és d'inserir vèrtexs en les arestes (per exemple, canviant • - • per • - • - •). Una formulació equivalent a aquest teorema és:

Un graf és pla si i només si no conté cap subgraf homeomorf a K 5 o K 3,3 .

Altres criteris per determinar si un graf és pla[modifica | modifica el codi]

A la pràctica, és difícil fer servir el teorema de Kuratowski per decidir ràpidament si un graf és pla. No obstant això, hi ha un algorisme ràpid per aquest problema: donat un graf de n vèrtexs i i el nombre d'arestes, és possible determinar en temps O (n) (lineal) si el graf és pla o no, utilitzant els dos teoremes següents:

Teorema 1. Si n ≥ 3 llavors i ≤ 3 n - 6
Teorema 2. Si n > 3 i no hi ha cicles de longitud 3, llavors i ≤ 2 n - 4

El graf K 3,3 , per exemple, té 6 vèrtexs, 9 arestes i cap cicle de longitud 3. Pel teorema 2, no pot ser pla. Noteu que aquests teoremes estan construïts amb una implicació unidireccional ( si ), i no bicondicional ( si i només si ) i per tant, només poden ser usats per a provar que el graf no és pla, però no que sigui pla. Si ambdós teoremes fallen, s'han d'usar altres mètodes.

Fórmula d'Euler[modifica | modifica el codi]

La fórmula d'Euler enuncia que si un graf connex, pla és dibuixat sobre un pla sense intersecció d'arestes, i sent v el nombre de vèrtexs, i el d' arestes i f la quantitat de cares (regions connectades per arestes, incloent la regió externa i infinita), aleshores:

v - i + f = 2,

Per exemple, la Característica d'Euler és 2. De manera més il·lustrativa, en els exemples anteriors, en el primer graf pla tenim: v = 6, i = 7 i f = 3. Si el segon graf es redibuixa sense les interseccions d'arestes, tenim v = 4, i = 6 i f = 4. La fórmula d'Euler es pot provar de la manera següent: si el graf no és un arbre, llavors s'elimina una aresta que completa un cicle. Això disminueix el valor de i i f en un, deixant v - i + f constant. Repetiu fins a arribar a un arbre. Els arbres tenen v = i +1 i f = 1, verificant la fórmula v - i + f = 2.

En un graf simple, connex i pla, qualsevol regió (possiblement exceptuant l'exterior) està connectada per almenys tres arestes i cada aresta toca com a molt dues regions. Usant la fórmula d'Euler, es pot demostrar que aquests grafs són escassos en el sentit que i ≤ 3 v - 6 si v ≥ 3.

Se li diu pla maximal al graf que és pla però en afegir qualsevol aresta deixés de ser-ho. Totes les regions (fins i tot l'externa) estan connectades per tres arestes, explicant la definició alternativa d' triangular per a aquest tipus de grafs. Si un graf triangular té v vèrtexs amb v > 2, aleshores té exactament 3 v - 6 arestes i 2 v - 4 regions.

Noteu que la fórmula d'Euler també és vàlida per poliedres simples. No és una casualitat: cada políedre simple es pot veure com un graf pla i connex usant els vèrtexs del políedre com vèrtexs del graf, i les arestes del políedre com arestes del graf. Les cares o regions del graf pla resultant corresponen a les cares del políedre. Per exemple, el segon graf pla de l'exemple correspon a un tetràedre. Alternativament, no tots els grafs plans i simples corresponen a un políedre (els arbres, per exemple). Un teorema de Ernst Steinitz diu que els grafs plans formats a partir de políedres convexos són precisament els grafs plans simples i triangulars.



Referències[modifica | modifica el codi]