En teoría de grafos , un grafo de Halin es un tipo de grafo 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 de modo que ninguno de sus bordes se cruce (esto se llama incrustación plana ), y el ciclo conecta las hojas en su orden en el sentido de las agujas del reloj en esta incrustación. Por lo tanto, el ciclo forma la cara exterior del grafo de Halin, con el árbol dentro de él. [1]
Los grafos de Halin reciben su nombre del matemático alemán Rudolf Halin , quien los estudió en 1971. [2] Los grafos de Halin cúbicos (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 grafos de Halin son grafos poliédricos , lo que significa que cada grafo de Halin se puede utilizar para formar los vértices y las aristas de un poliedro convexo , y los poliedros formados a partir de ellos se han llamado poliedros sin techo o domos .
Cada grafo de Halin tiene un ciclo hamiltoniano a través de todos sus vértices, así como ciclos de casi todas las longitudes hasta el número de vértices del grafo. Los grafos de Halin se pueden reconocer en tiempo lineal . Debido a que los grafos de Halin tienen un ancho de árbol bajo , muchos problemas computacionales que son difíciles en otros tipos de grafos planares, como encontrar ciclos hamiltonianos, se pueden resolver rápidamente en grafos de Halin.
Una estrella es un árbol con exactamente un vértice interno. La aplicación de la construcción del grafo de Halin a una estrella produce un grafo de rueda , el grafo de las (aristas de) una pirámide . [4] El grafo de un prisma triangular también es un grafo de Halin: se puede dibujar de manera 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 gráficos no triviales , [6] también es un gráfico de Halin. [7]
Todo grafo de Halin es 3-conexo , lo que significa que no es posible eliminar dos vértices de él y desconectar los vértices restantes. Es 3-conexo con aristas mínimas, lo que significa que si se elimina cualquiera de sus aristas, el grafo restante ya no será 3-conexo. [1] Por el teorema de Steinitz , como grafo plano 3-conexo, 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 grafo se puede elegir de modo que la cara que contiene todas las hojas del árbol sea horizontal, y todas las demás caras se encuentren por encima de ella, con pendientes iguales. [8] Al igual que con cada grafo poliédrico, los grafos de Halin tienen una incrustación plana única, hasta la elección de cuál de sus caras será la cara exterior. [1]
Todo grafo de Halin es un grafo hamiltoniano y cada arista del grafo pertenece a un ciclo hamiltoniano . Además, cualquier grafo 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 grafo de Halin contiene un triángulo. En particular, no es posible que un grafo de Halin sea un grafo sin triángulos ni un grafo bipartito . [10]
Más fuertemente, cada grafo de Halin es casi pancíclico , en el sentido de que tiene ciclos de todas las longitudes desde 3 hasta n con la posible excepción de un solo ciclo par. Además, cualquier grafo de Halin permanece casi pancíclico si se contrae una sola arista, y cada grafo de Halin sin vértices interiores de grado tres es pancíclico. [12]
El número cromático de incidencia de un grafo de Halin G con un 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 grafo y e es una arista incidente a 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 use el otro punto final de e . Para los grafos 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 comprobar si un grafo de n vértices dado es un grafo Halin en tiempo lineal , encontrando una incrustación planar del grafo (si existe una), y luego comprobando 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 grafo forma un árbol con los vértices de esta cara como sus hojas. Por otro lado, si no existe tal cara, entonces el grafo no es Halin. [15] Alternativamente, un grafo con n vértices y m aristas es Halin si y solo si es planar, 3-conexo, y tiene una cara cuyo número de vértices es igual al rango del circuito m − n + 1 del grafo, todo lo cual 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 depende de 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 planares arbitrarios, como encontrar un conjunto independiente máximo , se pueden resolver en tiempo lineal en gráficos de Halin utilizando 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, para probar si existe un subgrafo de Halin que incluya todos los vértices de un gráfico dado, o para probar si un gráfico dado es un subgrafo de un gráfico de Halin más grande. [20]
En 1971, Halin introdujo los grafos de Halin como una clase de grafos mínimamente conectados por 3 vértices: para cada arista del grafo, la eliminación de esa arista reduce la conectividad del grafo. [2] Estos grafos ganaron importancia con el descubrimiento de que muchos problemas algorítmicos que eran computacionalmente inviables para grafos planares arbitrarios podían resolverse eficientemente en ellos. [9] [16] Este hecho se explicó más tarde como 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 grafo de bajo ancho de árbol. [18] [19]
Antes del trabajo de Halin sobre estos grafos, los problemas de enumeración de grafos relativos a los grafos de Halin cúbicos (o 3-regulares ) fueron estudiados en 1856 por Thomas Kirkman [3] y en 1965 por Hans Rademacher . Rademacher llama a estos grafos poliedros basados . Los define como los grafos poliédricos cúbicos con f caras en las que una de las caras tiene f − 1 lados. [21] Los grafos que se ajustan a esta definición son exactamente los grafos de Halin cúbicos. [22]
Inspirados por el hecho de que tanto los grafos de Halin como los grafos planos conexos de 4 vértices contienen ciclos hamiltonianos, Lovász y Plummer (1974) conjeturaron que cada grafo plano conexo de 4 vértices contiene un subgrafo de Halin generador; aquí, "generador" significa que el subgrafo incluye todos los vértices del grafo más grande. La conjetura de Lovász-Plummer permaneció abierta hasta 2015, cuando se publicó una construcción para una cantidad infinita de contraejemplos. [23]
Los grafos de Halin también se denominan a veces árboles con faldón [11] o poliedros sin techo [9] , sin embargo, estos nombres son ambiguos. Algunos autores utilizan el nombre de "árboles con faldón" para referirse a grafos 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 los "poliedros con base", el nombre de "poliedros sin techo" también puede referirse a los grafos cúbicos de Halin [22] . Los poliedros convexos cuyos grafos son grafos de Halin también se han denominado domos [25] .