Graf pla
| Exemples de grafs | |
|---|---|
| Planar | No 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; K₅ i K3,3. Tots els grafs no plans contenen almenys un d'aquests subgrafs minimals.
En canvi, el graf complet K₄ é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 planars
[modifica]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'Euler
[modifica]
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.
- K₅ 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 Kuratowski
[modifica]
 |
 |
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 K₅ (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:
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é K₅ o K3,3 com a subgrafs.
- Un graf és planar si i només si no conté cap subdivisió que en ser escurçada inclogui K₅ 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é K₅ ni K3,3 com a subgrafs, però conté una subdivisió de K3,3 i al aplicar escurçaments se'n pot obtenir K₅ i K3,3, per tant no és planar.
Altres criteris per determinar si un graf és pla
[modifica]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
| Demostració del teorema 1 |
|---|
| Suposem el cas en el qual tenim un graf pla maximal amb n vèrtexs, m arestes i f cares.
Com que cada cara/regió està limitada per 3 arestes, i cada aresta delimita 2 cares, s'ha de complir que 3f ≤ 2m. Ara bé, partint de la fórmula d'Euler n − m f = 2, multiplicant-la per 3 obtenim 3n − 3m 3f = 6, si canviem 3f per 2m ens queda 3n − m >= 6, per tant m ≤ 3n - 6. Com que tot graf pla amb més de 3 vèrtexs pot ser triangular afegint arestes, tenim que 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
| Demostració del teorema 2 |
|---|
| Suposem el cas en el qual tenim un graf pla lliure de triangles, és a dir, sense cap subgraf isomorf a C₃, amb n vèrtexs, m arestes i f cares.
Les cares d'aquest graf han d'estar limitades per un cicle de longitud 4 o major, per tant 2m ≥ 4f. Partint novament de la fórmula d'Euler n − m f = 2, multiplicant-la per 4 obtenim 4n − 4m 4f = 8, aïllant 4f ens queda 4f = 8 - 4n 4m. Utilitzant la desigualtat anterior ens queda 2m ≥ 8 - 4n 4m, i per tant 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ències
[modifica]- ↑ 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].
- ↑ de Fraysseix, H.; Pach, J.; Pollack, R. «How to draw a planar graph on a grid». Combinatorica, 10, 1990.
- ↑ Apple, K. «Every planar map is four colorable». Illinois J. Math., 21, 1977, pàg. 429-567.
- ↑ Fàbrega, J.; Fiol, M. A. «Maximally connexted digraphs». J. Graph Theory, 13, 1989, pàg. 657-668.
- ↑ 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.
- ↑ 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.
- ↑ Haray, F.; Tutte, W.T. «A duel form of Kuratowski's theorem». Bull. Amer. Math. Soc., 21, 1, 1965, pàg. 168.
Bibliografia
[modifica]- 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 Arxivat 2006-07-15 a Wayback Machine.'. Journal of Graph Algorithms and Applications, vol. 8 no. 3, pp. 241-273. En anglès.
