Grafo Halin
From Wikipedia, the free encyclopedia
En teoría de grafos, un grafo Halin es un tipo de grafo plano que se construye 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 ninguna de sus aristas se cruce (esto se denomina 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 grafo de Halin, con el árbol en su interior.[1]
Los grafos de Halin deben su nombre al matemático alemán Rudolf Halin, que 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 puede utilizarse para formar los vértices y aristas de un poliedro convexo, y los poliedros formados a partir de ellos se han denominado poliedros sin techo o cúpulas.
Todo 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 pueden reconocerse en tiempo lineal. Dado que los grafos de Halin tienen poca anchura de árbol, muchos problemas computacionales que son difíciles de resolver en otros tipos de grafos planos, como la búsqueda de ciclos de Hamilton, pueden resolverse rápidamente en grafos de Halin.
Una estrella es un árbol con exactamente un vértice interno. Aplicando la construcción del grafo de Halin a una estrella se obtiene un grafo de rueda, el grafo de las (aristas de) una pirámide.[4] El grafo de un prisma triangular es también un grafo de Halin: se puede dibujar
de forma 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 grafo de Frucht, uno de los cinco grafos cúbicos más pequeños sin automorfismos gráficos no triviales,[6] también es un grafo de Halin.[7]
Propiedades
Todo grafo de Halin está conectado por 3, lo que significa que no es posible eliminar dos vértices de él y desconectar los vértices restantes. Es de 3 aristas mínimas, lo que significa que si se elimina alguna de sus aristas, el grafo restante deja de ser de 3 aristas.[1]Por el teorema de Steinitz, como grafo plano de 3 aristas, 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 puede elegirse de modo que la cara que contiene todas las hojas del árbol sea horizontal y todas las demás caras queden por encima de ella, con pendientes iguales.[8] Como todo grafo poliédrico, los grafos de Halin tienen una única incrustación plana, 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, todo 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 sin triángulos ni un grafo bipartito.[10]
Además, todo grafo de Halin es casi pancíclico, en el sentido de que tiene ciclos de todas las longitudes de 3 a n, con la posible excepción de una única longitud par. Además, todo 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.[11]
El número cromático de incidencia de un grafo Halin G con grado máximo Δ(G) mayor que cuatro es Δ(G) + 1.[12] 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 Halin con Δ(G) = 3 o 4, el número cromático de incidencia puede llegar a 5 o 6, respectivamente.[13]
Complejidad computacional
Es posible comprobar si un grafo de n vértices es un grafo de Halin en tiempo lineal, encontrando una incrustación plana del grafo (si existe) y comprobando si existe una cara que tenga al menos n/2 + 1 vértices, todos de grado tres. En caso afirmativo, 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.[14] Alternativamente, un grafo con n vértices y m aristas es Halin si y sólo si es plano, está conectado por 3 y tiene una cara cuyo número de vértices es igual al rango del circuito m - n + 1 del grafo, todo lo cual puede comprobarse en tiempo lineal.[15] Otros métodos para reconocer grafos 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 se basa en conocer la incrustación plana del grafo.[16]
Por lo tanto, muchos problemas de optimización de grafos que son NP-completos para grafos planos arbitrarios, como encontrar un conjunto independiente máximo, pueden resolverse en tiempo lineal en grafos Halin utilizando programación dinámica[18] o el teorema de Courcelle, o en algunos casos (como la construcción de ciclos Hamiltonianos) mediante algoritmos directos.[19] Sin embargo, es NP-completo encontrar el mayor subgrafo de Halin 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 mayor.[20]
