Grafo plano

Grafos de exemplo Plano Non plano100x100pxGrafo de bolboretas100x100pxGrafo completo K5100x100pxGrafo completo K4100x100pxGrafo de utilidade K3,3

Na teoría de grafos, un grafo plano é un grafo que se pode mergullar no plano, é dicir, pódese debuxar no plano de forma que as súas arestas se corten só nos seus extremos. 

Noutras palabras, pódese debuxar de forma que ningúnha aresta se cruce.

Todo grafo que se poida debuxar nun plano tamén se pode debuxar na esfera, e viceversa, mediante proxección estereográfica.

Os grafos planos pódense codificar mediante mapas combinatorios ou sistemas de rotación.

Os grafos planos xeneralízanse como grafos que se poden debuxar nunha superficie dun genus determinado. Nesta terminoloxía, os grafos planos teñen genus 0, xa que o plano (e a esfera) son superficies de genus 0. Consulte "mergullo de grafos" para outros temas relacionados.

 Criterios para ser plano 

 Teoremas de Kuratowski e Wagner 

 Un grafo finito é plano se e só se non contén un subgrafo que sexa unha subdivisión do grafo completo  ou do grafo bipartito completo  (grafo de utilidade).

Unha subdivisión dun grafo resulta de inserir vértices nas arestas (por exemplo, mudar unha aresta  cero ou máis veces.
miniatura| Un exemplo de grafo sen subgrafos  ou . Porén, contén unha subdivisión de  e, polo tanto, non é plana.
En lugar de considerar as subdivisións, o teorema de Wagner trata dos menores:

 Un  grafo finito é plano se e só se non ten  ou  como menor.

Un menor dun grafo resulta de tomar un subgrafo e contraer repetidamente unha aresta nun vértice, con cada veciño dos vértices finais orixinais converténdose nun veciño do novo vértice.
miniatura|484x484px| Unha animación que mostra que o grafo de Petersen contén un grafo menor isomorfo ao grafo  e, polo tanto, non é plano.
Klaus Wagner preguntou de xeito máis xeral se algunha clase de grafos pechados menores está determinada por un conxunto finito de "menores prohibidos". Este é agora o teorema de Robertson-Seymour, demostrado nunha longa serie de artigos. Na linguaxe deste teorema,  e  son os menores prohibidos para a clase de grafos planos finitos.

 Propiedades 

 Fórmula de Euler 
A característica de Euler indica que se se debuxa no plano un grafo plano, conexo e finito sen ningunha intersección de arestas, e  é o número de vértices,  é o número de arestas e  é o número de caras (rexións limitadas por arestas, incluída a rexión exterior infinitamente grande), entón



A modo de ilustración, no grafo de bolboreta mostrado na primeira figura, ,  e  (5-6+3=2). 

Nun grafo finito, conexo, simple e plano, calquera cara (excepto posibelmente a exterior) está limitada por polo menos tres arestas e cada aresta toca como máximo dúas caras, polo que ; usando a fórmula de Euler, pódese mostrar que estes grafos son escasos no sentido de que se :



miniatura| Un diagrama de Schlegel dun dodecaedro regular, formando un grafo plano a partir dun poliedro convexo.

 Grao medio 
Os grafos planos conexos con máis dunha aresta obedecen á desigualdade , porque cada cara ten polo menos tres incidencias cara-aresta e cada aresta aporta exactamente dúas incidencias. Dedúcese mediante transformacións alxébricas desta desigualdade coa fórmula de Euler  que para os grafos planos finitos o grao medio é estritamente inferior a 6. Os grafos con grao medio máis alto non poden ser planos.

 Grafos de moedas 
miniatura| Exemplo do teorema de empaquetamento circular en , o grafo completo en cinco vértices, menos unha aresta.
Dicimos que dous círculos debuxados nun plano se bican (ou osculan) sempre que coinciden nun único punto. Un "grafo de moedas" é un grafo formado por un conxunto de círculos, dos que non hai dous interiores superpostos, facendo un vértice para cada círculo e unha aresta para cada par de círculos que se bican. O teorema de empaquetamento circular, probado por primeira vez por Paul Koebe en 1936, afirma que un grafo é plano se e só se é un grafo de moedas.

 Densidade do grafo plano 
O coeficiente de retícula  ou densidade  dun grafo plano, ou rede, é a relación entre o número  de caras limitadas (o mesmo que o rango do circuíto do grafo, segundo o criterio de grafo plano de Mac Lane ) polos seus valores máximos posíbeis  para un grafo con  vértices:



A densidade obedece , con  para un grafo plano completamente escaso (unha árbore) e  para un grafo plano completamente denso (máximal).

 Grafo dual 
miniatura|146x146px| Un grafo plano e o seu dual
Dado un mergullo  dun grafo conexo (non necesariamente simple) no plano sen interseccións de arestas, construímos o grafo dual  do seguinte xeito: escollemos un vértice en cada cara de  (incluída a cara exterior) e para cada aresta  en  introducimos unha nova aresta en  que une os dous vértices en  correspondentes ás dúas caras de  que se atopan en  en G. 

A maiores, esta aresta debúxase de xeito que atravese  exactamente unha vez e que non corte ningunha outra aresta de  ou . Daquela  é de novo un mergullo dun grafo plano (non necesariamente simple); ten tantas arestas como , tantos vértices como  teña caras e tantas caras como  teña vértices. 

O termo "dual" xustifícase polo feito de que ; aquí a igualdade é a equivalencia de mergullos na esfera. Se  é o grafo plano correspondente a un poliedro convexo, entón  é o grafo plano correspondente ao poliedro dual.

Aínda que o dual construído para un mergullo particular é único (ata  isomorfismo), os grafos poden ter diferentes duais (é dicir, non isomorfos), obtidos a partir de diferentes mergullos (é dicir, non homeomorfos).

 Notas 


 Véxase tamén 

 Bibliografía 




  Special Issue on Graph Drawing



 Outros artigos 
 Mapa combinatorio 
 Aplanarización
 Problema das tres casas
 Ligazóns externas 
Edge Addition Planarity Algorithm Source Code, version 1.0  contén Edge Addition Planarity Algorithms, current version.
Public Implementation of a Graph Algorithm Library and Editor, GPL biblioteca de algoritmos de grafos que inclúe probas de grafos planos, megullador de grafos planos e exposición de subgrafos de Kuratowski en tempo linear.
Boost Graph Library tools for planar graphs, similar á anterior.
3 Utilidades de Puzzle e Grafos planos
NetLogo Planarity model,  NetLogo versión do xogo de John Tantalo

Categoría:Teoría de grafos
Categoría:Wikipedia:Páxinas con traducións non revisadas