Gráfico de Halin

En teoría de grafos , un grafo de Halin es un tipo de grafo planar , construido al conectar las hojas de un árbol formando 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 manera que ninguna de sus aristas se cruce (esto se denomina incrustación planar ), y el ciclo conecta las hojas en su orden en sentido horario en esta incrustación. Así, el ciclo forma la cara exterior del grafo de Halin, con el árbol en su interior. ^{[ 1 ]}

Los grafos de Halin reciben su nombre del matemático alemán Rudolf Halin , quien los estudió en 1971. ^{[ 2 ]} Los grafos 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 grafos de Halin son grafos poliédricos , lo que significa que cada grafo de Halin puede usarse 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 posee un ciclo hamiltoniano que pasa por 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 identificar en tiempo lineal . Debido a su baja anchura de árbol , muchos problemas computacionales que resultan difíciles en otros tipos de grafos planares, como la búsqueda de ciclos hamiltonianos, se pueden resolver rápidamente en grafos de Halin.

Un prisma triangular, construido como un grafo de Halin a partir de un árbol de seis vértices.

Gráficos de rueda

Una estrella es un árbol con un único vértice interno. Al aplicar la construcción de grafos de Halin a una estrella, se obtiene un grafo 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 internos y cinco aristas. ^{[ 5 ]}

El grafo de Frucht , uno de los cinco grafos cúbicos más pequeños sin automorfismos de grafos no triviales , ^{[ 6 ]} es también un grafo de Halin. ^{[ 7 ]}

Todo grafo de Halin es 3-conexo , lo que significa que no es posible eliminar dos vértices y desconectar los restantes. Es 3-conexo con aristas mínimas, lo que significa que si se elimina cualquiera de sus aristas, el grafo resultante ya no será 3-conexo. ^{[ 1 ]} Según el teorema de Steinitz , como grafo planar 3-conexo, puede representarse 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 puede elegirse 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 todo grafo poliédrico, los grafos de Halin tienen una incrustación planar única, salvo 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 tras la eliminación de cualquier vértice. ^{[ 9 ]} Dado que todo árbol sin vértices de grado 2 contiene dos hojas que comparten el mismo padre, todo grafo de Halin contiene un triángulo. En particular, no es posible que un grafo de Halin sea un grafo libre de triángulos ni un grafo bipartito . ^{[ 10 ]}

Más concretamente, todo grafo de Halin es casi pancíclico , en el sentido de que posee ciclos de todas las longitudes desde 3 hasta n , con la posible excepción de una única longitud par. Además, cualquier grafo de Halin sigue siendo casi pancíclico si se contrae una sola arista, y todo 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 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 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 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 ]}

Los números de diferentes gráficos de Halin en${\displaystyle n}$vértices, comenzando en${\displaystyle n=4}$(los más pequeños posibles), son: ^{[ 15 ]}

1, 1, 2, 2, 4, 6, 13, 22, 50, 106, 252, 589, 1475, 3669, 9435, 24345, ...

Esta enumeración cuenta dos grafos de Halin incrustados como iguales cuando son reflejos especulares uno del otro. Cuando los reflejos de grafos de Halin asimétricos se cuentan como distintos, los números se convierten en ^{[ 16 ].}

1, 1, 2, 2, 4, 7, 16, 32, 76, 181, 443, 1098, 2793, 7127, 18458, 48128, ...

Es posible comprobar en tiempo lineal si un grafo dado de n vértices es un grafo de Halin , encontrando una incrustación planar del grafo (si existe) 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 estas 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 hojas. Por otro lado, si no existe tal cara, entonces el grafo no es de Halin. ^{[ 17 ]} Alternativamente, un grafo con n vértices y m aristas es de 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. ^{[ 18 ]} Otros métodos para reconocer grafos de Halin en tiempo lineal incluyen la aplicación del teorema de Courcelle o un método basado en la reescritura de grafos , ninguno de los cuales depende de conocer la incrustación planar del grafo. ^{[ 19 ]}

Cada grafo de Halin tiene un ancho de árbol = 3. ^{[ 20 ]} Por lo tanto, muchos problemas de optimización de grafos que son NP-completos para grafos planares arbitrarios, como encontrar un conjunto independiente máximo , pueden resolverse en tiempo lineal en grafos de Halin usando programación dinámica ^{[ 21 ]} o el teorema de Courcelle, o en algunos casos (como la construcción de ciclos hamiltonianos ) por algoritmos directos. ^{[ 19 ]} Sin embargo, es NP-completo encontrar el subgrafo de Halin más grande de un grafo dado, probar si existe un subgrafo de Halin que incluya todos los vértices de un grafo dado, o probar si un grafo dado es un subgrafo de un grafo de Halin más grande. ^{[ 22 ]}

En 1971, Halin introdujo los grafos de Halin como una clase de grafos mínimamente conectados por 3 vértices: para cada arista en el grafo, la eliminación de esa arista reduce la conectividad del grafo. ^{[ 2 ]} Estos grafos cobraron 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 ] [ 18 ]} Este hecho se explicó más tarde como 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. ^{[ 20 ] [ 21 ]}

Antes del trabajo de Halin sobre estos grafos, los problemas de enumeración de grafos relacionados con los grafos cúbicos (o 3-regulares ) de Halin fueron estudiados en 1856 por Thomas Kirkman ^{[ 3 ]} y en 1965 por Hans Rademacher . Rademacher denomina a estos grafos poliedros basados . Los define como los grafos poliédricos cúbicos con f caras, en los que una de las caras tiene f − 1 lados. ^{[ 23 ]} Los grafos que se ajustan a esta definición son precisamente los grafos cúbicos de Halin. ^{[ 24 ]}

Inspirados por el hecho de que tanto los grafos de Halin como los grafos planares con 4 vértices conexos contienen ciclos hamiltonianos, Lovász y Plummer (1974) conjeturaron que todo grafo planar con 4 vértices conexos contiene un subgrafo de Halin generador; aquí, "generador" significa que el subgrafo incluye todos los vértices del grafo mayor. La conjetura de Lovász-Plummer permaneció abierta hasta 2015, cuando se publicó una construcción para infinitos contraejemplos. ^{[ 25 ]}

Los grafos 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 grafos planares formados a partir de árboles mediante la conexión de las hojas en un ciclo, pero sin requerir que los vértices internos del árbol tengan grado tres o más ^{[ 26 ]} . Y al igual que "poliedros con base", el nombre "poliedros sin techo" también puede referirse a los grafos cúbicos de Halin ^{[ 24 ]} . Los poliedros convexos cuyos grafos son grafos de Halin también se han denominado domos ^{[ 27 ]} .

• Gráficos de Halin , Sistema de información sobre inclusiones de clases de gráficos.