Gráfico plano
| Gráficos de ejemplo | |
|---|---|
| Planar | No planar |
 Gráfico de mariposas |  Gráfico completo K5 |
 Gráfico completo K4 |  Gráfico de Utilidad K3,3 |
En la teoría de grafos, un gráfico plano es un gráfico que se puede incrustar en el plano, es decir, se puede dibujar en el plano de tal manera que sus bordes se intersecan solo en sus puntos finales. En otras palabras, se puede dibujar de tal manera que ningún borde se cruce entre sí. Tal dibujo se llama gráfico plano o incrustación plana del gráfico. Un gráfico plano se puede definir como un gráfico plano con un mapeo desde cada nodo a un punto en un plano, y desde cada borde a una curva plana en ese plano, de modo que los puntos extremos de cada curva son los puntos mapeados desde su final. nodos, y todas las curvas son disjuntas excepto en sus puntos extremos.
Todo gráfico que se pueda dibujar en un plano se puede dibujar también en la esfera, y viceversa, mediante proyección estereográfica.
Los gráficos planos se pueden codificar mediante mapas combinatorios o sistemas de rotación.
Una clase de equivalencia de dibujos topológicamente equivalentes en la esfera, generalmente con supuestos adicionales como la ausencia de istmos, se denomina mapa plano. Aunque un gráfico plano tiene una cara externa o ilimitada, ninguna de las caras de un mapa plano tiene un estado particular.
Los gráficos planos se generalizan a gráficos dibujables en una superficie de un género determinado. En esta terminología, los gráficos planos tienen género 0, ya que el plano (y la esfera) son superficies de género 0. Consulte "incrustación de gráficos" para otros temas relacionados.
Criterios de planitud
Teoremas de Kuratowski y Wagner
El matemático polaco Kazimierz Kuratowski proporcionó una caracterización de los gráficos planos en términos de gráficos prohibidos, ahora conocido como el teorema de Kuratowski:
- Un gráfico finito es plano si y sólo si no contiene un subgrafo que es una subdivisión del gráfico completo K5 o el gráfico bipartito completo K3,3 (gráfico de utilidad).
Una subdivisión de un gráfico resulta de insertar vértices en los bordes (por ejemplo, cambiar un borde • —— • a • — • — •) cero o más veces.
En lugar de considerar subdivisiones, el teorema de Wagner trata con menores:
- Un gráfico finito es plano si no tiene K5 o K3,3 como menor.
Un gráfico menor resulta de tomar un subgráfico y contraer repetidamente un borde en un vértice, con cada vecino de los vértices finales originales convirtiéndose en vecino del nuevo vértice.
Klaus Wagner preguntó de manera más general si cualquier clase de gráficos cerrados menores está determinada por un conjunto finito de "menores prohibidos". Este es ahora el teorema de Robertson-Seymour, demostrado en una larga serie de artículos. En el lenguaje de este teorema, K5 y K3,3 son los menores prohibidos para la clase de grafos planos finitos.
Otros criterios
En la práctica, es difícil usar el criterio de Kuratowski para decidir rápidamente si un gráfico determinado es plano. Sin embargo, existen algoritmos rápidos para este problema: para un gráfico con n vértices, es posible determinar en el tiempo O(n) (tiempo lineal) si el gráfico puede ser plano o no (ver prueba de planaridad).
Para un gráfico plano simple, conectado, con vértices v y e bordes y f caras, las siguientes condiciones simples se cumplen para v ≥ 3:
- Teorema 1. e ≤ 3v - 6;
- Teorema 2. Si no hay ciclos de longitud 3, entonces e ≤ 2v – 4.
- Teorema 3. f ≤ 2v – 4.
En este sentido, los gráficos planos son gráficos dispersos, ya que solo tienen bordes O(v), asintóticamente menor que el máximo O(v2). El gráfico K3,3, por ejemplo, tiene 6 vértices, 9 aristas y ningún ciclo de longitud 3. Por lo tanto, por el Teorema 2, no puede ser plano. Estos teoremas proporcionan condiciones necesarias para la planaridad que no son condiciones suficientes y, por lo tanto, solo se pueden usar para demostrar que un gráfico no es plano, no que sea plano. Si tanto el teorema 1 como el 2 fallan, se pueden usar otros métodos.
- El criterio de la planaridad de Whitney da una caracterización basada en la existencia de un dual algebraico;
- El criterio de la planaridad de Mac Lane da una caracterización algebraica de gráficos plano finitos, a través de sus espacios de ciclo;
- El criterio de la planaridad Fraysseix-Rosenstiehl da una caracterización basada en la existencia de una bipartición de los bordes del coárbol de un árbol de búsqueda de profundidad. Es central en el algoritmo de prueba de planaridad izquierda-derecha;
- El teorema de Schnyder da una caracterización de la planaridad en términos de dimensión de orden parcial;
- El criterio de planaridad de Colin de Verdière da una caracterización basada en la máxima multiplicidad del segundo valor de ciertos operadores Schrödinger definidos por el gráfico.
- El teorema Hanani-Tutte afirma que un gráfico es planario si y sólo si tiene un dibujo en el que cada par independiente de bordes cruza un número uniforme de veces; se puede utilizar para caracterizar los gráficos plano a través de un sistema de ecuaciones modulo 2.
Propiedades
Fórmula de Euler
La fórmula de Euler establece que si se dibuja un gráfico plano, conectado y finito en el plano sin ninguna intersección de bordes, y v es el número de vértices, e es el número de aristas y f es el número de caras (regiones delimitadas por bordes, incluida la región exterior infinitamente grande), luego
Como ilustración, en el gráfico de mariposa anterior, v = 5, e< /i> = 6 y f = 3. En general, si la propiedad se cumple para todos los gráficos planos de caras f, cualquier cambio en el gráfico que cree una cara adicional manteniendo el gráfico plano mantendría v – e + f como invariante. Dado que la propiedad se cumple para todos los gráficos con f = 2, por inducción matemática se cumple para todos los casos. La fórmula de Euler también se puede demostrar de la siguiente manera: si el gráfico no es un árbol, elimine un borde que complete un ciclo. Esto reduce tanto e como f por uno, dejando v – e + f constante. Repita hasta que el gráfico restante sea un árbol; los árboles tienen v = e + 1 y f = 1, produciendo v – e + f = 2, i. es decir, la característica de Euler es 2.
En un gráfico plano finito, conexo, simple, cualquier cara (excepto posiblemente la exterior) está delimitada por al menos tres aristas y cada arista toca como máximo dos caras; Usando la fórmula de Euler, se puede mostrar que estos gráficos son dispersos en el sentido de que si v ≥ 3:
La fórmula de Euler también es válida para poliedros convexos. Esto no es una coincidencia: cada poliedro convexo se puede convertir en un gráfico plano simple conectado usando el diagrama de Schlegel del poliedro, una proyección en perspectiva del poliedro en un plano con el centro de perspectiva elegido cerca del centro de uno de los Caras de poliedro. No todos los gráficos planos corresponden a un poliedro convexo de esta manera: los árboles, por ejemplo, no. El teorema de Steinitz dice que los gráficos poliédricos formados a partir de poliedros convexos son precisamente los gráficos planares simples finitos de 3 conexiones. De manera más general, la fórmula de Euler se aplica a cualquier poliedro cuyas caras sean polígonos simples que formen una superficie topológicamente equivalente a una esfera, independientemente de su convexidad.
Grado medio
Los gráficos planos conexos con más de una arista obedecen a la desigualdad 2e ≥ 3f, porque cada cara tiene al menos tres incidencias cara-arista y cada arista contribuye exactamente con dos incidencias. Se sigue a través de transformaciones algebraicas de esta desigualdad con la fórmula de Euler v – e + f = 2 que para gráficos planos finitos, el grado promedio es estrictamente menor que 6. Los gráficos con un grado promedio mayor no pueden ser planos.
Gráficos de monedas
Decimos que dos círculos dibujados en un plano se besan (o osculan) siempre que se cortan en exactamente un punto. Un "gráfico de monedas" es un grafo formado por un conjunto de círculos, de los cuales dos no tienen interiores superpuestos, haciendo un vértice para cada círculo y una arista para cada par de círculos que se besan. El teorema de empaquetamiento circular, demostrado por primera vez por Paul Koebe en 1936, establece que un gráfico es plano si y solo si es un gráfico de monedas.
Este resultado proporciona una prueba fácil del teorema de Fáry, que cada gráfico plano simple se puede incrustar en el plano de tal manera que sus bordes sean segmentos de línea recta que no se cruzan entre sí. Si uno coloca cada vértice del gráfico en el centro del círculo correspondiente en una representación de gráfico de monedas, entonces los segmentos de línea entre los centros de los círculos que se besan no cruzan ninguno de los otros bordes.
Densidad gráfica plana
El coeficiente de mallado o densidad D de un gráfico plano, o red, es la relación del número f – 1 de caras delimitadas (igual que el rango del circuito del gráfico, según el criterio de planaridad de Mac Lane) por sus valores máximos posibles 2v – 5 para un gráfico con v vértices:
La densidad obedece a 0 ≤ D ≤ 1, con D = 0 para un gráfico plano completamente disperso (un árbol) y D = 1 para un gráfico plano completamente denso (máximo).
Gráfica doble
(feminine)
Dada una G incrustada de un gráfico conectado (no necesariamente simple) en el plano sin intersecciones de bordes, construimos el < i>gráfico dual G* de la siguiente manera: elegimos un vértice en cada cara de G (incluida la cara exterior) y para cada arista e en G introducimos una nueva ventaja en G* conectando los dos vértices en G* correspondientes a las dos caras en G que se encuentran en e. Además, este borde se dibuja de modo que cruce e exactamente una vez y que ningún otro borde de G o G* se cruzan. Entonces G* es nuevamente la incrustación de un gráfico plano (no necesariamente simple); tiene tantas aristas como G, tantos vértices como G tiene caras y tantas caras como G tiene vértices. El término "doble" se justifica por el hecho de que G** = G; aquí la igualdad es la equivalencia de incrustaciones en la esfera. Si G es el gráfico plano correspondiente a un poliedro convexo, entonces G* es el gráfico plano correspondiente al poliedro dual.
Los gráficos duales son útiles porque muchas propiedades del gráfico dual están relacionadas de forma sencilla con las propiedades del gráfico original, lo que permite probar los resultados sobre los gráficos mediante el examen de sus gráficos duales.
Si bien el dual construido para una incrustación en particular es único (hasta el isomorfismo), los gráficos pueden tener duales diferentes (es decir, no isomorfos), obtenidos a partir de incrustaciones diferentes (es decir, no homeomorfas).
Familias de grafos planos
Gráficos planos máximos
Un gráfico simple se llama planar máximo si es plano pero agregar cualquier borde (en el conjunto de vértices dado) destruiría esa propiedad. Todas las caras (incluida la exterior) quedan delimitadas por tres aristas, lo que explica el término alternativo triangulación plana. Los nombres alternativos "gráfico triangular" o "gráfico triangulado" también se han utilizado, pero son ambiguos, ya que se refieren más comúnmente al gráfico lineal de un gráfico completo y a los gráficos cordales respectivamente. Cada gráfico plano máximo es al menos 3-conexo.
Si un gráfico plano maximal tiene v vértices con v > 2, entonces tiene precisamente 3v – 6 bordes y 2v – 4 caras.
Las redes apolínicas son los gráficos planos máximos formados al dividir repetidamente caras triangulares en triples de triángulos más pequeños. De manera equivalente, son los 3-árboles planos.
Los gráficos estrangulados son aquellos en los que cada ciclo periférico es un triángulo. En un gráfico plano maximal (o más generalmente un gráfico poliédrico) los ciclos periféricos son las caras, por lo que los gráficos planos maximales están estrangulados. Los grafos estrangulados incluyen también los grafos cordales, y son exactamente los grafos que se pueden formar por clique-sumas (sin borrar aristas) de grafos completos y grafos planares máximos.
Gráficos extraplanares
Los gráficos outerplanares son gráficos con una incrustación en el plano tal que todos los vértices pertenecen a la cara ilimitada de la incrustación. Cada gráfico de plano exterior es plano, pero lo contrario no es cierto: K4 es plano pero no plano exterior. Un teorema similar al de Kuratowski establece que un grafo finito es plano externo si y solo si no contiene una subdivisión de K4 o de K2,3. Lo anterior es un corolario directo del hecho de que un gráfico G es plano exterior si el gráfico formado a partir de G agregando un nuevo vértice, con bordes que lo conectan con todos los demás vértices, es un gráfico plano.
Una incrustación en un plano exterior de un gráfico es lo mismo que una incrustación en un plano exterior. Para k > 1 una incrustación plana es k-outerplanar si eliminar los vértices en la cara exterior da como resultado una (k – 1)-incrustación de planos exteriores. Un gráfico es k-outerplanar si tiene un k-incrustación de planos exteriores.
Gráficos de Halin
Un grafo de Halin es un grafo formado a partir de un árbol plano no dirigido (sin nodos de grado dos) conectando sus hojas en un ciclo, en el orden dado por el plano incrustado del árbol. De manera equivalente, es un gráfico poliédrico en el que una cara es adyacente a todas las demás. Todo grafo de Halin es plano. Al igual que los gráficos planos exteriores, los gráficos de Halin tienen un ancho de árbol bajo, lo que hace que muchos problemas algorítmicos en ellos se resuelvan más fácilmente que en los gráficos planos sin restricciones.
Gráficos planos ascendentes
Un gráfico plano ascendente es un gráfico acíclico dirigido que se puede dibujar en el plano con sus bordes como curvas que no se cruzan y que se orientan constantemente en dirección ascendente. No todos los gráficos acíclicos dirigidos planos son planos hacia arriba, y es NP-completo para probar si un gráfico dado es plano hacia arriba.
Gráficos planos convexos
Se dice que un gráfico plano es convexo si todas sus caras (incluida la cara exterior) son polígonos convexos. No todos los gráficos planos tienen una incrustación convexa (por ejemplo, el gráfico bipartito completo K2,4). Una condición suficiente para que un gráfico se pueda dibujar de forma convexa es que sea una subdivisión de un gráfico plano conectado por 3 vértices. El teorema del resorte de Tutte incluso establece que para gráficos planos simples de 3 vértices conectados, la posición de los vértices internos se puede elegir para que sea el promedio de sus vecinos.
Gráficos planos representables por palabras
Los gráficos planos representables con palabras incluyen gráficos planos sin triángulos y, de manera más general, gráficos planos de tres colores, así como ciertas subdivisiones de caras de gráficos de cuadrícula triangular y ciertas triangulaciones de gráficos de cilindros cubiertos de cuadrícula.
Teoremas
Enumeración de grafos planos
El asintotico para el número de gráficos planar (marcados) en vertices es , donde y .
Casi todos los gráficos planos tienen un número exponencial de automorfismos.
El número de gráficos planos no etiquetados (no isómorfos) sobre vertices es entre y .
Otros resultados
El teorema de los cuatro colores establece que cada gráfico plano tiene 4 colores (es decir, 4 partes).
El teorema de Fáry establece que todo gráfico plano simple admite una representación como un gráfico de línea recta plana. Un conjunto de puntos universal es un conjunto de puntos tal que cada gráfico plano con n vértices tiene tal incrustación con todos los vértices en el conjunto de puntos; existen conjuntos de puntos universales de tamaño cuadrático, formados tomando un subconjunto rectangular de la red de enteros. Todo grafo plano exterior simple admite una incrustación en el plano tal que todos los vértices se encuentran en un círculo fijo y todos los bordes son segmentos de línea recta que se encuentran dentro del disco y no se intersecan, por lo que n-vértice los polígonos regulares son universales para grafos planos exteriores.
La conjetura de Scheinerman (ahora un teorema) establece que cada gráfico plano se puede representar como un gráfico de intersección de segmentos de línea en el plano.
El teorema del separador plano establece que cada gráfico plano de n-vértice se puede dividir en dos subgráficos de tamaño máximo 2n/3 mediante la eliminación de O(< span class="nowrap">√n) vértices. Como consecuencia, los gráficos planos también tienen un ancho de árbol y un ancho de rama O(√n).
El teorema de la estructura del producto plano establece que cada gráfico plano es un subgráfico del producto gráfico fuerte de un gráfico de ancho de árbol como máximo 8 y un camino. Este resultado se ha utilizado para mostrar que los gráficos planos tienen un número de cola acotado, un número cromático no repetitivo acotado y gráficos universales de tamaño casi lineal. También tiene aplicaciones para la clasificación de vértices. y coloración centrada en p de grafos planos.
Para dos grafos planos con vértices v, es posible determinar en el tiempo O(v) si son isomorfos o no (ver también problema de isomorfismo de grafos).
Generalizaciones
Un gráfico de vértice es un gráfico que puede volverse plano eliminando un vértice, y un gráfico de k-ápice es un gráfico que puede volverse plano eliminando como máximo k vértices.
Un gráfico de 1 plano es un gráfico que se puede dibujar en el plano con un cruce simple por arista como máximo, y un gráfico k-planar es un gráfico que se puede dibujar con como máximo k cruces simples por arista.
Un gráfico de mapa es un gráfico formado a partir de un conjunto finito de regiones disjuntas interiores simplemente conectadas en el plano mediante la conexión de dos regiones cuando comparten al menos un punto límite. Cuando a lo sumo tres regiones se encuentran en un punto, el resultado es un gráfico plano, pero cuando cuatro o más regiones se encuentran en un punto, el resultado puede ser no plano.
Un gráfico toroidal es un gráfico que se puede incrustar sin cruces en el toroide. De manera más general, el género de un gráfico es el género mínimo de una superficie bidimensional en la que se puede incrustar el gráfico; los gráficos planos tienen género cero y los gráficos toroidales no planos tienen género uno.
Cualquier gráfico se puede incrustar en un espacio tridimensional sin cruces. Sin embargo, un análogo tridimensional de los gráficos planos lo proporcionan los gráficos incrustables sin enlaces, gráficos que pueden incrustarse en el espacio tridimensional de tal manera que no hay dos ciclos topológicamente vinculados entre sí. En analogía con las caracterizaciones de Kuratowski y Wagner de los gráficos planos como gráficos que no contienen K5 o K3,3 como elemento secundario, los gráficos integrables sin enlaces se pueden caracterizar como los gráficos que no contienen como elemento secundario ninguno de los siete gráficos de la familia Petersen. En analogía con las caracterizaciones de los gráficos planos y exteriores como gráficos con Colin de Verdière invariante como máximo dos o tres, los gráficos incrustables sin enlaces son los gráficos que tienen Colin de Verdière invariante como máximo cuatro.