Conde halina

En teoría de grafos, un gráfico de Halin es una especie de gráfico plano que se construye a partir de un árbol que tiene al menos 4 vértices, ninguno de los cuales tiene exactamente dos vecinos. El árbol se dibuja en el plano para que ningún borde se cruce, luego se agregan bordes para conectar todas sus hojas en un ciclo [1] . Los recuentos de Halin llevan el nombre del matemático alemán Rudolf Halin .quien las estudió en 1971 [2] , pero las gráficas cúbicas de Halin habían sido estudiadas un siglo antes por el matemático inglés Thomas Kirkman[3] .

Edificio

El grafo de Halin se construye de la siguiente manera: sea un plano  - árbol incrustado con cuatro o más vértices de modo que ningún vértice del grafo tenga grado dos (es decir, ningún vértice tiene exactamente dos vecinos). El gráfico de Halin se crea agregando un ciclo al gráfico que recorre todas las hojas de tal manera que el camino de expansión permanece plano.

Ejemplos

Una estrella  es un árbol con un solo vértice interno. Aplicando la construcción de Halin, obtenemos una rueda , un gráfico piramidal . Un gráfico de prisma triangular también es un gráfico de Halin: se puede dibujar de modo que una de sus caras rectangulares sea un ciclo exterior y los bordes restantes formen un árbol con cuatro hojas, dos vértices internos y cinco bordes.

El gráfico de Frucht , uno de los dos gráficos cúbicos más pequeños con automorfismos no triviales , también es un gráfico de Halin.

Propiedades

Cualquier gráfico de Halin tiene 3 conexiones , lo que significa que no se puede dividir un gráfico en dos gráficos eliminando dos vértices. También tiene aristas mínimamente 3 conectadas, lo que significa que después de eliminar cualquier arista, el gráfico ya no tiene 3 conexiones [1] . Por el teorema de Steinitz , al ser un gráfico plano de 3 conexiones, el gráfico de Halin se puede representar como un conjunto de vértices y aristas de un poliedro convexo . Así, es un grafo de un poliedro , pero en este caso, como para cualquier grafo de un poliedro, su empotramiento en el plano es único hasta la elección de una cara que será su cara exterior [1] .

Cualquier gráfico de Halin es un gráfico hamiltoniano y cualquier arista pertenece a un ciclo hamiltoniano. Además, cualquier gráfico de Halin sigue siendo hamiltoniano después de eliminar cualquier vértice [4] . Dado que cualquier árbol sin vértices de grado 2 contiene dos hojas con el mismo padre, cualquier gráfico de Halin contiene un triángulo. En particular, el gráfico de Halin no puede ser un gráfico sin triángulos ni un gráfico bipartito . Más estrictamente, cualquier gráfico 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 longitud par. Además, cualquier gráfico de Halin permanece casi pancíclico después de la contracción de un borde, y cualquier gráfico de Halin sin vértices interiores de grado tres es pancíclico [5] .

Cualquier gráfico de Halin tiene un ancho de árbol de tres [6] como máximo . Por lo tanto, muchos problemas de optimización que son NP-completos para grafos arbitrarios, como encontrar el conjunto independiente para grafos de Halin, se pueden resolver en tiempo lineal usando programación dinámica [7] .

El dual débil de un gráfico planar anidado tiene vértices correspondientes a las caras del gráfico planar y aristas correspondientes a las caras adyacentes (el dual débil se obtiene a partir del dual eliminando el vértice correspondiente a la cara exterior). El grafo dual débil del conde Halin siempre es biconexo y exterior . Esta propiedad se puede usar para caracterizar los gráficos de Halin: un gráfico plano incrustado en un plano es un gráfico de Halin con un ciclo de hojas como la cara exterior de la incrustación si y solo si su dual débil está doblemente conectado y es plano exterior [8] .

Historia

En 1971, Halin propuso los gráficos (llamados gráficos de Halin) como una clase de gráficos mínimos de 3 vértices conectados: para cada borde del gráfico, su eliminación reduce la conectividad [2] . Estos gráficos adquirieron un significado especial cuando se hizo evidente que muchos problemas algorítmicos que son imposibles de resolver para gráficos planos arbitrarios pueden resolverse de manera eficiente en gráficos de Halin [4] [8] , lo que luego se explicó como consecuencia de su pequeño ancho de árbol [ 6] [7 ] .

Antes del trabajo de Halin, el problema de enumerar los gráficos cúbicos de Halin fue abordado en 1856 por Thomas Kirkman.[3] , y en 1965 por Hans Rademacher [9] Rademacher llamó a estos grafos basados ​​en poliedros . Los definió como grafos cúbicos de politopos con f caras, una de cuyas caras tiene f − 1 aristas. Los gráficos que satisfacen esta definición son exactamente los gráficos cúbicos de Halin.

Los gráficos de Halin también se denominan a veces poliedros sin techo [4] pero, al igual que el nombre "basado en politopos", este nombre se puede atribuir a los gráficos de Halin cúbicos [10] . Los poliedros convexos cuyas gráficas son gráficas de Halin también se denominan cúpulas [11] .

Notas

  1. ↑ 1 2 3 Encyclopaedia of Mathematics , primer volumen complementario, 1988, ISBN 0-7923-4709-9 , p. 281, artículo "Halin Graph" Archivado el 11 de enero de 2014 en Wayback Machine .
  2. ↑ 1 2 Halín. Matemáticas combinatorias y sus aplicaciones (Proc. Conf., Oxford, 1969). - Londres: Academic Press, 1971. - pp. 129-136 .
  3. ↑ 1 2  
  4. ↑ 1 2 3 , DOI 10.1007/BF02591867 
  5. ↑ Skowronska. Ciclos en grafos. - Elsevier Science Publishers BV, 1985. - T. 27. - S. 179-194. - (Anales de Matemáticas Discretas).
  6. ↑ 12 Hans Bodlaender . Gráficos planos con ancho de árbol acotado . - Departamento de Ciencias de la Computación, Universidad de Utrecht , 1988. - (Informe Técnico RUU-CS-88-14).
  7. ↑ 12 Hans Bodlaender . Actas del XV Coloquio Internacional sobre Autómatas, Lenguajes y Programación. - Springer-Verlag, 1988. - T. 317. - S. 105-118. — (Apuntes de clase en informática).
  8. ↑ 1 2 Maciej M. Sysło, Andrzej Proskurowski. Teoría de grafos: Actas de una conferencia celebrada en Lagów, Polonia, del 10 al 13 de febrero de 1981. - Springer-Verlag, 1983. - Vol. 1018. - P. 248-256. — (Apuntes de clase en Matemáticas). -doi : 10.1007/ BFb0071635 .
  9. ↑ Hans Rademacher. Sobre el número de ciertos tipos de poliedros // Illinois Journal of Mathematics. - 1965. - T. 9 . - S. 361-380 .
  10. ↑ L. Lovász, MD Plummer. Combinatoria (Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973). Londres: Universidad de Cambridge. Prensa, 1974. - S. 103-107. Matemáticas de Londres. soc. Serie de apuntes de conferencias, n.º 13 _
  11. ↑ Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara. Actas de la 25.ª Conferencia Canadiense sobre Geometría Computacional (CCCG 2013), Waterloo, Ontario, Canadá, del 8 al 10 de agosto de 2013–2013–págs. 43–48.

Enlaces