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 thumb|200x200px|Proba sen palabras de que un grafo hipercubo non é plano usando os teoremas de Kuratowski ou Wagner e atopando os subgrafos K5 (arriba) ou K3,3 (abaixo). O matemático polaco Kazimierz Kuratowski proporcionou unha caracterización dos grafos planos en termos de grafos prohibidos, agora coñecido como teorema de Kuratowski:

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