En teoría de grafos , un gráfico de Halin es un tipo de gráfico plano , construido conectando las hojas de un árbol en un ciclo. El árbol debe tener al menos cuatro vértices, ninguno de los cuales tiene exactamente dos vecinos; debe dibujarse en el plano para que ninguno de sus bordes se cruce (esto se llama incrustación plana ), y el ciclo conecta las hojas en el orden de las agujas del reloj en esta incrustación. Así, el ciclo forma la cara exterior del gráfico de Halin, con el árbol en su interior. [1]
Los gráficos de Halin llevan el nombre del matemático alemán Rudolf Halin , quien los estudió en 1971. [2] Los gráficos cúbicos de Halin (aquellos en los que cada vértice toca exactamente tres aristas) ya habían sido estudiados más de un siglo antes por Kirkman . [3] Los gráficos de Halin son gráficos poliédricos , lo que significa que cada gráfico de Halin se puede utilizar para formar los vértices y aristas de un poliedro convexo , y los poliedros formados a partir de ellos se han llamado poliedros o cúpulas sin techo .
Cada gráfico de Halin tiene un ciclo hamiltoniano que recorre todos sus vértices, así como ciclos de casi todas las longitudes hasta el número de vértices del gráfico. Los gráficos de Halin se pueden reconocer en tiempo lineal . Debido a que los gráficos de Halin tienen un ancho de árbol bajo , muchos problemas computacionales que son difíciles en otros tipos de gráficos planos, como encontrar ciclos hamiltonianos, se pueden resolver rápidamente en los gráficos de Halin.
Una estrella es un árbol con exactamente un vértice interno. La aplicación de la construcción del gráfico de Halin a una estrella produce un gráfico de rueda , el gráfico de los (bordes de) una pirámide . [4] La gráfica de un prisma triangular es también una gráfica de Halin: se puede dibujar de modo que una de sus caras rectangulares sea el ciclo exterior, y las aristas restantes formen un árbol con cuatro hojas, dos vértices interiores y cinco aristas. [5]
El gráfico de Frucht , uno de los cinco gráficos cúbicos más pequeños sin automorfismos de gráficos no triviales , [6] también es un gráfico de Halin. [7]
Cada gráfico de Halin tiene 3 conexiones , lo que significa que no es posible eliminar dos vértices y desconectar los vértices restantes. Tiene un borde mínimo con 3 conexiones, lo que significa que si se elimina cualquiera de sus aristas, el gráfico restante ya no estará con 3 conexiones. [1] Según el teorema de Steinitz , como gráfico plano de 3 conexos, se puede representar como el conjunto de vértices y aristas de un poliedro convexo ; es decir, es un grafo poliédrico . El poliedro que realiza el gráfico se puede elegir de modo que la cara que contiene todas las hojas del árbol sea horizontal y todas las demás caras queden encima de ella, con pendientes iguales. [8] Como ocurre con todos los gráficos poliédricos, los gráficos de Halin tienen una incrustación plana única, hasta la elección de cuál de sus caras será la cara exterior. [1]
Cada gráfico de Halin es un gráfico hamiltoniano y cada arista del gráfico pertenece a un ciclo hamiltoniano . Además, cualquier gráfico de Halin sigue siendo hamiltoniano después de la eliminación de cualquier vértice. [9] Debido a que cada árbol sin vértices de grado 2 contiene dos hojas que comparten el mismo padre, cada gráfico de Halin contiene un triángulo. En particular, no es posible que un gráfico de Halin sea un gráfico sin triángulos ni un gráfico bipartito . [10]
Más claramente, cada gráfico de Halin es casi pancíclico , en el sentido de que tiene ciclos de todas las longitudes desde 3 an con la posible excepción de una sola longitud par. Además, cualquier gráfico de Halin permanece casi pancíclico si se contrae una sola arista, y todo gráfico de Halin sin vértices interiores de grado tres es pancíclico. [12]
El número cromático de incidencia de un gráfico de Halin G con grado máximo Δ( G ) mayor que cuatro es Δ( G ) + 1 . [13] Este es el número de colores necesarios para colorear todos los pares ( v , e ) donde v es un vértice del gráfico y e es un borde incidente con v , obedeciendo ciertas restricciones en la coloración. Los pares que comparten un vértice o que comparten una arista no pueden tener el mismo color. Además, un par ( v , e ) no puede tener el mismo color que otro par que utilice el otro extremo de e . Para gráficos de Halin con Δ ( G ) = 3 o 4 , el número cromático de incidencia puede ser tan grande como 5 o 6 respectivamente. [14]
Es posible probar si un gráfico de n vértices dado es un gráfico de Halin en tiempo lineal , encontrando una incrustación plana del gráfico (si existe) y luego probando si existe una cara que tenga al menos n /2 + 1 vértices, todos de grado tres. Si es así, puede haber como máximo cuatro de esas caras, y es posible comprobar en tiempo lineal para cada una de ellas si el resto del gráfico forma un árbol con los vértices de esta cara como sus hojas. Por otro lado, si no existe tal cara, entonces el gráfico no es Halin. [15] Alternativamente, un gráfico con n vértices y m aristas es Halin si y solo si es plano, conexo 3 y tiene una cara cuyo número de vértices es igual al rango del circuito m − n + 1 del gráfico, todos que se puede comprobar en tiempo lineal. [16] Otros métodos para reconocer gráficos de Halin en tiempo lineal incluyen la aplicación del teorema de Courcelle , o un método basado en la reescritura de gráficos , ninguno de los cuales se basa en conocer la incrustación plana del gráfico. [17]
Cada gráfico de Halin tiene un ancho de árbol = 3. [18] Por lo tanto, muchos problemas de optimización de gráficos que son NP-completos para gráficos planos arbitrarios, como encontrar un conjunto independiente máximo , pueden resolverse en tiempo lineal en gráficos de Halin usando programación dinámica [19] o el teorema de Courcelle, o en algunos casos (como la construcción de ciclos hamiltonianos ) mediante algoritmos directos. [17] Sin embargo, es NP-completo encontrar el subgrafo de Halin más grande de un gráfico dado, probar si existe un subgrafo de Halin que incluya todos los vértices de un gráfico dado, o probar si un gráfico dado es un subgrafo de un gráfico de Halin más grande. [20]
En 1971, Halin introdujo los gráficos de Halin como una clase de gráficos mínimamente conectados con 3 vértices: para cada borde del gráfico, la eliminación de ese borde reduce la conectividad del gráfico. [2] Estos gráficos ganaron importancia con el descubrimiento de que muchos problemas algorítmicos que eran computacionalmente inviables para gráficos planos arbitrarios podían resolverse eficientemente en ellos. [9] [16] Más tarde se explicó que este hecho era una consecuencia de su bajo ancho de árbol y de metateoremas algorítmicos como el teorema de Courcelle que proporcionan soluciones eficientes a estos problemas en cualquier gráfico de bajo ancho de árbol. [18] [19]
Antes del trabajo de Halin en estos gráficos, los problemas de enumeración de gráficos relacionados con los gráficos cúbicos (o 3 regulares ) de Halin fueron estudiados en 1856 por Thomas Kirkman [3] y en 1965 por Hans Rademacher . Rademacher llama a estos gráficos basados en poliedros . Los define como gráficos poliédricos cúbicos con f caras en las que una de las caras tiene f − 1 lados. [21] Las gráficas que se ajustan a esta definición son exactamente las gráficas cúbicas de Halin. [22]
Inspirándose en el hecho de que tanto los gráficos de Halin como los gráficos planos de 4 vértices conectados contienen ciclos hamiltonianos, Lovász y Plummer (1974) conjeturaron que cada gráfico plano de 4 vértices conectados contiene un subgrafo de Halin que se extiende; aquí "que abarca" significa que el subgrafo incluye todos los vértices del gráfico más grande. La conjetura de Lovász-Plummer permaneció abierta hasta 2015, cuando se publicó una construcción para una infinidad de contraejemplos. [23]
Los gráficos de Halin a veces también se denominan árboles con faldón [11] o poliedros sin techo . [9] Sin embargo, estos nombres son ambiguos. Algunos autores utilizan el nombre "árboles con faldón" para referirse a gráficos planos formados a partir de árboles conectando las hojas en un ciclo, pero sin exigir que los vértices internos del árbol tengan grado tres o más. [24] Y al igual que "poliedros basados", el nombre "poliedros sin techo" también puede referirse a los gráficos cúbicos de Halin. [22] Los poliedros convexos cuyas gráficas son gráficas de Halin también han sido llamadas cúpulas . [25]