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 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. Por tanto, el ciclo forma la cara exterior del gráfico de Halin, con el árbol dentro. [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 bordes, 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 los bordes de un poliedro convexo , y los poliedros formados a partir de ellos se denominan poliedros o cúpulas sin techo .
Cada gráfico de Halin tiene un ciclo hamiltoniano a través de todos sus vértices, así como ciclos de casi todas las longitudes hasta su número de vértices. 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 para otros tipos de gráficos planos, como encontrar ciclos hamiltonianos, también se pueden resolver rápidamente en los gráficos de Halin.
Ejemplos de
Una estrella es un árbol con exactamente un vértice interno. Aplicar 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 también es una gráfica de Halin: se puede dibujar de modo que una de sus caras rectangulares sea el ciclo exterior y los bordes restantes formen un árbol con cuatro hojas, dos vértices interiores y cinco bordes. [5]
El gráfico de Frucht , uno de los cinco gráficos cúbicos más pequeños sin automorfismos de gráfico no triviales , [6] también es un gráfico de Halin. [7]
Propiedades
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 de 3 conectados, lo que significa que si se elimina cualquiera de sus bordes, el gráfico restante ya no estará conectado en 3. [1] Según el teorema de Steinitz , como un gráfico plano de 3 conexiones, se puede representar como el conjunto de vértices y aristas de un poliedro convexo ; es decir, es un gráfico poliédrico . Y, como ocurre con todos los gráficos poliédricos, su incrustación plana es ú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 borde 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. [8] 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 . [9]
Más fuertemente, cada gráfico Halin es casi pancyclic , en el sentido de que tiene ciclos de todas las longitudes de 3 a n con la posible excepción de una longitud incluso solo. Además, cualquier gráfico de Halin permanece casi pancíclico si se contrae un solo borde, y todo gráfico de Halin sin vértices interiores de grado tres es pancíclico. [11]
El número cromático de incidencia de un gráfico 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 gráfico, ye es un borde incidente av , obedeciendo ciertas restricciones sobre el color. Los pares que comparten un vértice o que comparten un borde no pueden tener el mismo color. Además, un par ( v , e ) no puede tener el mismo color que otro par que usa 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. [13]
Complejidad computacional
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 tiene al menos n / 2 + 1 vértices, todos de grado tres. Si es así, puede haber como máximo cuatro caras de este tipo, 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 rostro, entonces el gráfico no es Halin. [14] Alternativamente, un gráfico con n vértices y m aristas es Halin si y solo si es plano, conectado en 3 y tiene una cara cuyo número de vértices es igual al rango del circuito m - n + 1 del gráfico, todos de que se puede comprobar en tiempo lineal. [15] 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. [dieciséis]
Cada gráfico de Halin tiene un ancho de árbol = 3. [17] 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 [18] o el teorema de Courcelle, o en algunos casos (como la construcción de ciclos hamiltonianos ) mediante algoritmos directos. [16] 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 incluye 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. [19]
Historia
En 1971, Halin introdujo las gráficas de Halin como una clase de gráficas con conexión mínima de 3 vértices: para cada borde en el 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 podrían resolverse eficientemente en ellos. [8] [15] 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 gráfico de bajo ancho de árbol. [17] [18]
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 . [20] Rademacher llama a estos poliedros basados en gráficos . Los define como las gráficas poliédricas cúbicas con f caras en las que una de las caras tiene f - 1 lados. Las gráficas que se ajustan a esta definición son exactamente las gráficas cúbicas de Halin.
Inspirados por el hecho de que tanto los gráficos de Halin como los gráficos planos conectados a 4 vértices contienen ciclos hamiltonianos, Lovász y Plummer (1974) conjeturaron que cada gráfico plano conectado a 4 vértices contiene un subgrafo de Halin que se extiende; aquí "abarcando" 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 infinitos contraejemplos. [21]
Los gráficos de Halin a veces también se denominan árboles con faldones [10] o poliedros sin techo . [8] Sin embargo, estos nombres son ambiguos. Algunos autores usan 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 requerir que los vértices internos del árbol tengan un grado tres o más. [22] Y como "poliedros basados", el nombre de "poliedros sin techo" también puede referirse a los gráficos cúbicos de Halin. [23] Los poliedros convexos cuyos gráficos son gráficos de Halin también se han llamado cúpulas . [24]
Referencias
- ^ a b c Enciclopedia de Matemáticas , primer volumen suplementario, 1988, ISBN 0-7923-4709-9 , p. 281, artículo "Halin Graph" y referencias en el mismo.
- ^ a b Halin, R. (1971), "Estudios sobre grafos mínimamente n conectados", Matemáticas combinatorias y sus aplicaciones (Proc. Conf., Oxford, 1969) , Londres: Academic Press, págs. 129-136, MR 0278980.
- ^ a b Kirkman, Th. P. (1856), "Sobre la enumeración de x -edra que tiene cumbres de tryral y una base ( x - 1 ) -gonal", Transacciones filosóficas de la Royal Society de Londres , 146 : 399-411, doi : 10.1098 / rstl. 1856.0018 , JSTOR 108592.
- ↑ Cornuéjols, Naddef & Pulleyblank (1983) : "Si T es una estrella, es decir, un solo nodo v unido a n otros nodos, entonces H se llama rueda y es el tipo más simple de gráfico de Halin".
- ^ Véase Sysło y Proskurowski (1983) , Prop. 4.3, p. 254, que identifica el prisma triangular como el gráfico único con exactamente tres ciclos que puede ser el ciclo externo de una realización como un gráfico de Halin.
- ^ Bussemaker, FC; Cobeljic, S .; Cvetkovic, DM; Seidel, JJ (1976), Investigación informática de gráficos cúbicos , informe EUT, 76-WSK-01, Departamento de Matemáticas y Ciencias de la Computación, Universidad Tecnológica de Eindhoven
- ^ Weisstein, Eric W. , "Halin Graph" , MathWorld
- ^ a b c Cornuéjols, G .; Naddef, D .; Pulleyblank, WR (1983), "Gráficos de Halin y el problema del viajante", Programación matemática , 26 (3): 287-294, doi : 10.1007 / BF02591867.
- ^ Vea la prueba del teorema 10 en Wang, Weifan; Bu, Yuehua; Montassier, Mickaël; Raspaud, André (2012), "On backbone coloring of graphs", Journal of Combinatorial Optimization , 23 (1): 79–93, doi : 10.1007 / s10878-010-9342-6 , MR 2875236: "Dado que G contiene un ciclo de 3 que consta de un vértice interno y dos vértices externos, G no es un gráfico bipartito".
- ^ a b Malkevitch, Joseph (1978), "Duración de ciclo en grafos politopales", Teoría y aplicaciones de grafos (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976) , Lecture Notes in Mathematics, Berlín: Springer , 642 : 364–370, doi : 10.1007 / BFb0070393 , ISBN 978-3-540-08666-6, MR 0491287
- ^ Skowrońska, Mirosława (1985), "La panciclicidad de los gráficos de Halin y sus contracciones exteriores", en Alspach, Brian R .; Godsil, Christopher D. (eds.), Cycles in Graphs , Annals of Discrete Mathematics, 27 , Elsevier Science Publishers BV, págs. 179–194.
- ^ Wang, Shu-Dong; Chen, Dong-Ling; Pang, Shan-Chen (2002), "El número de coloración de incidencia de las gráficas de Halin y las gráficas planas externas", Matemáticas discretas , 256 (1–2): 397–405, doi : 10.1016 / S0012-365X (01) 00302-8 , Señor 1927561.
- ^ Shiu, WC; Sun, PK (2008), "Pruebas inválidas sobre coloración de incidencia", Matemáticas discretas , 308 (24): 6575–6580, doi : 10.1016 / j.disc.2007.11.030 , MR 2466963.
- ^ Fomin, Fedor V .; Thilikos, Dimitrios M. (2006), "Una aproximación de 3 para el ancho de ruta de los gráficos de Halin", Journal of Discrete Algorithms , 4 (4): 499–510, doi : 10.1016 / j.jda.2005.06.004 , MR 2577677.
- ^ a b Sysło, Maciej M .; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Actas de una conferencia celebrada en Lagów, Polonia, del 10 al 13 de febrero de 1981 , Lecture Notes in Mathematics, 1018 , Springer-Verlag, págs. 248-256, doi : 10.1007 / BFb0071635.
- ^ a b Eppstein, David (2016), "Reconocimiento simple de gráficos de Halin y sus generalizaciones", Journal of Graph Algorithms and Applications , 20 (2): 323–346, arXiv : 1502.05334 , doi : 10.7155 / jgaa.00395.
- ^ a b Bodlaender, Hans (1988), Gráficos planos con ancho de árbol acotado (PDF) , Informe técnico RUU-CS-88-14, Departamento de Ciencias de la Computación, Universidad de Utrecht , archivado desde el original (PDF) el 28 de julio de 2004.
- ^ a b Bodlaender, Hans (1988), "Programación dinámica en gráficos con ancho de árbol acotado", Actas del XV Coloquio Internacional sobre Autómatas, Lenguajes y Programación , Lecture Notes in Computer Science, 317 , Springer-Verlag, págs. 105-118, doi : 10.1007 / 3-540-19488-6_110 , ISBN 978-3540194880.
- ^ Horton, SB; Parker, R. Gary (1995), "On Halin subgraphs and supergraphs", Discrete Applied Mathematics , 56 (1): 19–35, doi : 10.1016 / 0166-218X (93) E0131-H , MR 1311302.
- ^ Rademacher, Hans (1965), "Sobre el número de ciertos tipos de poliedros", Illinois Journal of Mathematics , 9 (3): 361–380, doi : 10.1215 / ijm / 1256068140 , MR 0179682.
- ^ Chen, Guantao; Enomoto, Hikoe; Ozeki, Kenta; Tsuchiya, Shoichi (2015), "Triangulaciones planas sin un subgrafo de Halin que se extienda: contraejemplos de la conjetura de Lovász-Plummer sobre los gráficos de Halin", SIAM Journal on Discrete Mathematics , 29 (3): 1423-1426, doi : 10.1137 / 140971610 , MR 3376776.
- ^ Skowrońska, M .; Sysło, MM (1987), "Ciclos hamiltonianos en árboles con faldones", Actas de la Conferencia Internacional sobre Análisis Combinatorio y sus Aplicaciones (Pokrzywna, 1985), Zastos. Estera. , 19 (3–4): 599–610 (1988), MR 0951375
- ^ Lovász, L .; Plummer, MD (1974), "Sobre una familia de gráficos bicríticos planos", Combinatoria (Proc. British Combinatorial Conf., Univ. Coll. Gales, Aberystwyth, 1973) , Londres: Cambridge Univ. Press, págs. 103-107. London Math. Soc. Lecture Note Ser., No. 13, MR 0351915.
- ^ Demaine, Erik D .; Demaine, Martin L .; Uehara, Ryuhei (2013), "Cremallera desplegada de cúpulas y prismoides", Actas de la 25ª Conferencia Canadiense sobre Geometría Computacional (CCCG 2013), Waterloo, Ontario, Canadá, 8 al 10 de agosto de 2013 , págs. 43–48.
enlaces externos
- Gráficos de Halin , Sistema de información sobre inclusiones de clases de gráficos.