Graf pla

(S'ha redirigit des de: Graf planar)

En teoria de grafs, un graf pla o planar és un graf que pot ser dibuixat en un pla sense que les arestes s'intersequin (o utilitzant una definició més formal, que aquest graf pugui ser "embegut" en un pla).[1][2] Un graf no és pla si no pot ser dibuixat sobre un pla sense que les seves arestes s'intersequin. Hi ha dos grafs no plans minimals; K5 i K3,3. Tots els grafs no plans contenen almenys un d'aquests subgrafs minimals.

Exemples de grafs
Planar No planar
Graf planar
K5
K4
K3,3

En canvi, el graf complet K4 és pla, perquè pot ser redibuixat sense que les arestes es creuin, passant una de les diagonals per l'exterior.

Per poder comprovar la planaritat d'un graf, primer s'ha d'adequar a una sèrie de criteris bàsics:

  • El graf és connex. Si tenim un graf inconnex, podem considerar cada part com a graf connex independent.
  • No té cap vèrtex de grau 1. Si conté vèrtexs de grau 1, per tant amb una sola aresta, aquests es poden eliminar de l'estructura sense risc a modificar-ne la planaritat.

Propietats dels grafs planarsModifica

Els grafs planars tenen una sèrie de propietats que els fa interessants.

  • Són fàcils de visualitzar.
  • Es poden pintar amb 4 colors o menys.[3]
  • Se'ls poden aplicar vàries operacions de forma eficient.
  • Es poden emmagatzemar eficientment emprant arbres SPQR.

Teorema d'EulerModifica

 
Representació de les arestes dels grafs no planars K5 i K3,3

Donat un graf pla connex amb n vèrtexs, m arestes i f cares (regions connectades per arestes, incloent la regió externa i infinita) aleshores:

n - m + f = 2

És a dir, la Característica d'Euler és 2.

  • K5 no és planar perquè té n = 5, m = 10 > 3n - 6 = 9
  • K3,3 és bipartit, per tant no té cap cicle amb llargària imparella i per tant si fos planar no tindria cap cara triangular.[4] Per tant, K3,3 no és planar perquè té n = 6, m = 9 > 2n - 4 = 8

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 m i f en un, deixant n - m + f constant. Aquest procés es repeteix fins a arribar a un arbre. Els arbres tenen n = (m + 1) i f = 1, verificant la fórmula n - m + f = 2.

En un graf simple, connex i pla, qualsevol regió interna 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 m ≤ 3n - 6 si n ≥ 3.[5]

Si un graf és pla però al afegir qualsevol aresta deixaria de ser-ho, s'anomena pla maximal. Un pla maximal és triangular, ja que totes les regions (fins i tot l'externa) estan connectades per tres arestes. Si un graf triangular té n vèrtexs amb n > 2, aleshores té exactament 3n - 6 arestes i 2n - 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.[6] 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). Segons el teorema de Ernst Steinitz, els grafs plans formats a partir de políedres convexos són precisament els grafs plans simples i triangulars.

Teorema de KuratowskiModifica

 
Esquema de subgrafs no planars. Subdivisó de K5: Cicle amb punts ABC interconnectats a través de dos vèrtexs addicionals. Subdivisó de K3,3: Cicle amb punts ABCD que formen un parell de nanses (A-C, B-D), cadascuna de les quals té un vèrtex que la connecta amb l'altra.
 
Subdivisió i escurçament són contraris.
 
Escurçaments del graf de Petersen per obtenir K5 o K3,3

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

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

Una formulació equivalent a aquest teorema és:

Un graf és pla si i només si no conté cap subgraf homeomorfa K5 o K3,3.[7]

Altres característiques dels grafs relacionades descrites per Kuratowski són:

  • Al subdividir o escurçar un graf en conserva la planaritat.
  • Un graf és planar si i només si no conté K5 o K3,3 com a subgrafs.
  • Un graf és planar si i només si no conté cap subdivisió que al ser escurçada inclogui K5 o K3,3.

Subdivisió (afegir un vèrtex) i escurçament (treure un vèrtex) són complementaris. En cap cas modifiquen la planaritat de la figura, però fan més complexa la tasca de comprovació de la planaritat. Per exemple, el graf de Petersen no conté K5 ni K3,3 com a subgrafs, però conté una subdivisió de K3,3 i al aplicar escurçaments se'n pot obtenir K5 i K3,3, per tant no és planar.

Altres criteris per determinar si un graf és plaModifica

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 m 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 m ≤ 3n - 6
Representació planar d'un octaedre; n = 6, m = 12. És un graf planar maximal perquè m = 3n - 6, i triangular perquè cada cara veu 3 vèrtexs i està delimitada per 3 arestes; tots els cicles són de longitud 3.
Teorema 2. Si n > 3 i no hi ha cicles de longitud 3, llavors m ≤ 2n - 4
Representació planar d'un cub; n = 8, m = 12. Tots els cicles són de longitud 4, i es compleix que m = 2n - 4.

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.

Vegeu tambéModifica

ReferènciesModifica

  1. Dalfó, Cristina; Fiol, Miquel À. «Grafs, amics i coneguts». Butlletí de la Societat Catalana de Matemàtiques, 25, 1, 2010, pàg. 5-29. DOI: 10.2436/20.2002.01.25 [Consulta: 16 febrer 2020].
  2. de Fraysseix, H.; Pach, J.; Pollack, R. «How to draw a planar graph on a grid». Combinatorica, 10, 1990.
  3. Apple, K. «Every planar map is four colorable». Illinois J. Math., 21, 1977, pàg. 429-567.
  4. Fàbrega, J.; Fiol, M. A. «Maximally connexted digraphs». J. Graph Theory, 13, 1989, pàg. 657-668.
  5. Even, S.; Lempel, A.; Ceberdraum, I. «An algorithm for planarity testing of graphs». In Theory of Graphs: Internat. Symposium (Rome 1966), New York, Gordon and Breach, 1997, pàg. 215-232.
  6. Fiol, M. A.; Garriga, E. «From local adjacency polynomials to locally pseudo-distance-regular graphs». J. Combin. Theory Ser. B, 71, 1997, pàg. 162-183.
  7. Haray, F.; Tutte, W.T. «A duel form of Kuratowski's theorem». Bull. Amer. Math. Soc., 21, 1, 1965, pàg. 168.

BibliografiaModifica

  • Kazimierz Kuratowski (1930), Sur le problème des courbes gauche en topologie, Fund. Math., 15, pàg. 271-283.
  • K. Wagner (1937), Über eine Eigenschaften der Ebene Komplex, Math. Ann. 114, pàg. 570-590.
  • K. Wagner (1937), Über eine erweiterung eines satzes von Kuratowski, Deutsche Mathematik, 2, pàg. 280-285.
  • John M. Boyer and Wendy J. Myrvold (2005), 'On the cutting edge: Simplified O(n) planarity by edge addition'. Journal of Graph Algorithms and Applications, vol. 8 no. 3, pp. 241-273. En anglès.
A Wikimedia Commons hi ha contingut multimèdia relatiu a: Graf pla