Gráfico cuyos subgrafos inducidos preservan la distancia
Un gráfico de distancia-herencia.
En teoría de grafos , una rama de las matemáticas discretas , un grafo hereditario de distancias (también llamado grafo completamente separable ) [1] es un grafo en el que las distancias en cualquier subgrafo inducido conexo son las mismas que en el grafo original. Por lo tanto, cualquier subgrafo inducido hereda las distancias del grafo más grande.
Los gráficos hereditarios de distancia fueron nombrados y estudiados por primera vez por Howorka (1977), aunque Olaru y Sachs ya habían demostrado en 1970 que una clase equivalente de gráficos era perfecta . [2]
Se sabe desde hace algún tiempo que los gráficos hereditarios de distancia constituyen una clase de intersección de gráficos , [3] pero no se conocía ningún modelo de intersección hasta que Gioan y Paul (2012) lo dieron.
Definición y caracterización
La definición original de un grafo hereditario de distancia es un grafo G tal que, si dos vértices u y v pertenecen a un subgrafo inducido conexo H de G , entonces algún camino más corto que conecte u y v en G debe ser un subgrafo de H , de modo que la distancia entre u y v en H sea la misma que la distancia en G .
Los gráficos hereditarios de distancia también se pueden caracterizar de varias otras formas equivalentes: [4]
Son los grafos en los que todo camino inducido es un camino más corto, o equivalentemente los grafos en los que todo camino no más corto tiene al menos una arista que conecta dos vértices de caminos no consecutivos.
Son los grafos en los que cada ciclo de longitud cinco o más tiene al menos dos diagonales que se cruzan.
Son los grafos en los que, para cada cuatro vértices u , v , w y x , al menos dos de las tres sumas de distancias d ( u , v ) + d ( w , x ) , d ( u , w ) + d ( v , x ) y d ( u , x ) + d ( v , w ) son iguales entre sí.
Son los grafos que no tienen como subgrafos isométricos ningún ciclo de longitud cinco o más, ni ninguno de otros tres grafos: un 5-ciclo con una cuerda, un 5-ciclo con dos cuerdas que no se cruzan, y un 6-ciclo con una cuerda que conecta vértices opuestos.
Tres operaciones mediante las cuales se puede construir cualquier grafo hereditario de distancia.
Son los grafos que se pueden construir a partir de un solo vértice mediante una secuencia de las tres operaciones siguientes, como se muestra en la ilustración:
Agrega un nuevo vértice colgante conectado por un solo borde a un vértice existente del gráfico.
Reemplazar cualquier vértice del grafo por un par de vértices, cada uno de los cuales tiene el mismo conjunto de vecinos que el vértice reemplazado. El nuevo par de vértices se denomina falso gemelo entre sí.
Reemplazar cualquier vértice del grafo por un par de vértices, cada uno de los cuales tiene como vecinos a los vecinos del vértice reemplazado junto con el otro vértice del par. El nuevo par de vértices se denominan gemelos verdaderos entre sí.
Son los grafos que pueden descomponerse completamente en camarillas y estrellas ( grafos bipartitos completos K 1, q ) mediante una descomposición dividida . En esta descomposición, se encuentra una partición del grafo en dos subconjuntos, de modo que las aristas que separan los dos subconjuntos forman un subgrafo bipartito completo , se forman dos grafos más pequeños reemplazando cada uno de los dos lados de la partición por un único vértice, y se particionan recursivamente estos dos subgrafos. [5]
Son los grafos que tienen un ancho de rango uno, donde el ancho de rango de un grafo se define como el mínimo, sobre todas las particiones jerárquicas de los vértices del grafo, del rango máximo entre ciertas submatrices de la matriz de adyacencia del grafo determinada por la partición. [6]
Son los grafos libres de HHDG, lo que significa que tienen una caracterización de grafo prohibido según la cual ningún subgrafo inducido puede ser una casa (el grafo complementario de un grafo de trayectoria de cinco vértices ), un agujero (un grafo de ciclo de cinco o más vértices), un dominó (ciclo de seis vértices más una arista diagonal entre dos vértices opuestos) o una gema (ciclo de cinco vértices más dos diagonales incidentes al mismo vértice).
Relación con otras familias de gráficos
Todo grafo hereditario de la distancia es un grafo perfecto , [7] más específicamente un grafo perfectamente ordenable [8] y un grafo de Meyniel . Todo grafo hereditario de la distancia es también un grafo de paridad , un grafo en el que cada dos caminos inducidos entre el mismo par de vértices tienen ambos una longitud impar o ambos tienen una longitud par. [9] Toda potencia par de un grafo hereditario de la distancia G (es decir, el grafo G 2 i formado conectando pares de vértices a una distancia de como máximo 2 i en G ) es un grafo cordal . [10]
Cada grafo hereditario de distancia puede representarse como el grafo de intersección de cuerdas en un círculo, formando un grafo circular . Esto puede verse construyendo el grafo agregando vértices colgantes, falsos gemelos y verdaderos gemelos, en cada paso construyendo un conjunto correspondiente de cuerdas que representan el grafo. Agregar un vértice colgante corresponde a agregar una cuerda cerca de los puntos finales de una cuerda existente de modo que cruce solo esa cuerda; agregar falsos gemelos corresponde a reemplazar una cuerda por dos cuerdas paralelas que cruzan el mismo conjunto de otras cuerdas; y agregar verdaderos gemelos corresponde a reemplazar una cuerda por dos cuerdas que se cruzan entre sí pero son casi paralelas y cruzan el mismo conjunto de otras cuerdas.
Un grafo hereditario de distancia es bipartito si y solo si no tiene triángulos . Los grafos hereditarios de distancia bipartitos se pueden construir a partir de un único vértice añadiendo solo vértices colgantes y gemelos falsos, ya que cualquier gemelo verdadero formaría un triángulo, pero las operaciones de vértice colgante y gemelos falsos preservan la bipartición. Todo grafo hereditario de distancia bipartito es bipartito cordal y modular . [11]
Los grafos que pueden construirse a partir de un único vértice mediante vértices colgantes y gemelos verdaderos, sin ninguna operación de falsos gemelos, son casos especiales de los grafos ptolemaicos e incluyen los grafos de bloques . Los grafos que pueden construirse a partir de un único vértice mediante operaciones de falsos gemelos y gemelos verdaderos, sin ningún vértice colgante, son los cografos , que por lo tanto son hereditarios de la distancia; los cografos son exactamente las uniones disjuntas de grafos hereditarios de la distancia de diámetro 2. La vecindad de cualquier vértice en un grafo hereditario de la distancia es un cografo. El cierre transitivo del grafo dirigido formado al elegir cualquier conjunto de orientaciones para los bordes de cualquier árbol es hereditario de la distancia; el caso especial en el que el árbol está orientado de manera consistente lejos de algún vértice forma una subclase de grafos hereditarios de la distancia conocidos como grafos trivialmente perfectos , que también se denominan cografos cordales. [12]
Algoritmos
Los gráficos hereditarios de distancia se pueden reconocer y analizar en una secuencia de operaciones de vértices colgantes y gemelos en tiempo lineal. [13]
Debido a que los grafos hereditarios de distancia son perfectos, algunos problemas de optimización se pueden resolver en tiempo polinomial para ellos a pesar de ser NP-hard para clases más generales de grafos. Por lo tanto, es posible en tiempo polinomial encontrar la camarilla máxima o el conjunto independiente máximo en un grafo hereditario de distancia, o encontrar una coloración de grafo óptima de cualquier grafo hereditario de distancia. [14]
Debido a que los grafos hereditarios de distancia son grafos circulares , heredan algoritmos de tiempo polinomial para grafos circulares; por ejemplo, es posible determinar en tiempo polinomial el ancho de árbol de cualquier grafo circular y, por lo tanto, de cualquier grafo hereditario de distancia. [15]
Además, el ancho de camarilla de cualquier grafo hereditario de distancia es como máximo tres. [16] Como consecuencia, por el teorema de Courcelle , existen algoritmos de programación dinámica eficientes para muchos problemas en estos grafos. [17]
Varios otros problemas de optimización también pueden resolverse de manera más eficiente utilizando algoritmos diseñados específicamente para grafos hereditarios de distancia. Como muestran D'Atri y Moscarini (1988), se puede encontrar un conjunto dominante conexo mínimo (o equivalentemente un árbol de expansión con el máximo número posible de hojas) en tiempo polinomial en un grafo hereditario de distancia. También se puede encontrar un ciclo hamiltoniano o una ruta hamiltoniana de cualquier grafo hereditario de distancia en tiempo polinomial. [18]
Notas
^ Martillo y Maffray (1990).
^ Olaru y Sachs demostraron la α-perfección de los grafos en los que cada ciclo de longitud cinco o más tiene un par de diagonales que se cruzan (Sachs 1970, Teorema 5). Según Lovász (1972), la α-perfección es una forma equivalente de definición de grafos perfectos.
^ McKee y McMorris (1999)
^ Howarka (1977); Bandelt y Mulder (1986); Martillo y Maffray (1990); Brandstädt, Le y Spinrad (1999), Teorema 10.1.1, pág. 147.
^ Gioan y Paul (2012). Eppstein, Goodrich y Meng (2006) utilizaron una descomposición estrechamente relacionada para el dibujo de gráficos y Hui, Schaefer y Štefankovič (2004) utilizaron una descomposición estrechamente relacionada para el dibujo de gráficos hereditarios de distancia bipartitos.
^ Oum (2005).
^ Howorka (1977).
^ Brandstädt, Le y Spinrad (1999), págs. 70–71 y 82.
^ Brandstädt, Le y Spinrad (1999), p.45.
^ Brandstädt, Le & Spinrad (1999), Teorema 10.6.14, p.164.
^ Gráficos hereditarios de distancia bipartitos, Sistema de información sobre clases de gráficos y sus inclusiones, recuperado el 30 de septiembre de 2016.
^ Cornelsen y Di Stéfano (2005).
^ Damiand, Habib y Paul (2001); Gioan y Paul (2012). Hammer y Maffray (1990) propusieron una limitación temporal lineal anterior, pero Damiand descubrió que era errónea.
^ Cogis y Thierry (2005) presentan un algoritmo directo simple para conjuntos independientes ponderados máximos en grafos hereditarios de distancia, basado en el análisis del grafo en vértices colgantes y gemelos, corrigiendo un intento previo de dicho algoritmo por Hammer y Maffray (1990). Debido a que los grafos hereditarios de distancia son perfectamente ordenables, se pueden colorear de manera óptima en tiempo lineal utilizando LexBFS para encontrar un orden perfecto y luego aplicar un algoritmo de coloración voraz .
^ Kloks (1996); Brandstädt, Le y Spinrad (1999), pág. 170.
^ Golumbic y Rotics (2000).
^ Courcelle, Makowski y Rotics (2000); Espelage, Gurski y Wanke (2001).
^ Hsieh y col. (2002); Müller y Nicolai (1993).
Referencias
Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986), "Gráficos hereditarios de distancia", Journal of Combinatorial Theory , Serie B, 41 (2): 182–208, doi : 10.1016/0095-8956(86)90043-2 , MR 0859310.
Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Clases de grafos: un estudio , Monografías SIAM sobre matemáticas discretas y aplicaciones, ISBN 0-89871-432-X.
Cogis, O.; Thierry, E. (2005), "Cálculo de conjuntos estables máximos para grafos hereditarios de distancia", Optimización discreta , 2 (2): 185–188, doi : 10.1016/j.disopt.2005.03.004 , MR 2155518.
Cornelsen, Sabine; Di Stefano, Gabriele (2005), "Gráficos de comparabilidad en forma de árbol: caracterización, reconocimiento y aplicaciones", Proc. 30th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2004) , Lecture Notes in Computer Science , vol. 3353, Springer-Verlag, págs. 46–57, doi :10.1007/978-3-540-30559-0_4, MR 2158633, S2CID 14166894, ISBN 9783540241324 , 9783540305590 .
Courcelle, B. ; Makowski, JA; Rotics, U. (2000), "Problemas de optimización resolubles en tiempo lineal en gráficos con ancho de camarilla acotado", Theory of Computing Systems , 33 (2): 125–150, doi :10.1007/s002249910009, S2CID 15402031.
D'Atri, Alessandro; Moscarini, Marina (1988), "Gráficos hereditarios de distancia, árboles de Steiner y dominación conectada", SIAM Journal on Computing , 17 (3): 521–538, doi :10.1137/0217032, MR 0941943.
Damiand, Guillaume; Habib, Michel; Paul, Christophe (2001), "Un paradigma simple para el reconocimiento de grafos: aplicación a cografos y grafos hereditarios de distancia" (PDF) , Theoretical Computer Science , 263 (1–2): 99–111, doi :10.1016/S0304-3975(00)00234-6, MR 1846920.
Espelage, W.; Gurski, F.; Wanke, E. (2001), "Cómo resolver problemas de grafos NP-hard en grafos acotados por ancho de camarilla en tiempo polinomial", Proc. 27th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2001) , Lecture Notes in Computer Science , vol. 2204, Springer-Verlag, págs. 117–128.
Gioan, Emeric; Paul, Christophe (2012), "Descomposición dividida y árboles etiquetados con grafos: caracterizaciones y algoritmos completamente dinámicos para grafos totalmente descomponibles", Discrete Applied Mathematics , 160 (6): 708–733, arXiv : 0810.1823 , doi :10.1016/j.dam.2011.05.007, S2CID 6528410.
Golumbic, Martin Charles ; Rotics, Udi (2000), "Sobre el ancho de camarilla de algunas clases de grafos perfectos", International Journal of Foundations of Computer Science , 11 (3): 423–443, doi :10.1142/S0129054100000260, MR 1792124.
Howorka, Edward (1977), "Una caracterización de los grafos hereditarios de distancia", The Quarterly Journal of Mathematics , Segunda serie, 28 (112): 417–420, doi :10.1093/qmath/28.4.417, MR 0485544.
Hsieh, Sun-yuan; Ho, Chin-wen; Hsu, Tsan-sheng; Ko, Ming-tat (2002), "Algoritmos eficientes para el problema hamiltoniano en grafos hereditarios de distancia", Computing and Combinatorics: 8th Annual International Conference, COCOON 2002 Singapur, 15-17 de agosto de 2002, Actas , Lecture Notes in Computer Science , vol. 2387, Springer-Verlag, págs. 51-75, doi :10.1007/3-540-45655-4_10, ISBN 978-3-540-43996-7, Sr. 2064504.
Kloks, T. (1996), "Ancho de árbol de gráficos circulares", Revista internacional de fundamentos de la informática , 7 (2): 111–120, doi :10.1142/S0129054196000099.
Lovász, László (1972), "Hipergrafos normales y la conjetura del grafo perfecto", Discrete Mathematics , 2 (3): 253–267, doi : 10.1016/0012-365X(72)90006-4 , MR 0302480.
McKee, Terry A.; McMorris, FR (1999), Temas de teoría de grafos de intersección , Monografías SIAM sobre matemáticas discretas y aplicaciones, vol. 2, Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas, doi : 10.1137/1.9780898719802, ISBN 0-89871-430-3, Sr. 1672910
Müller, Haiko; Nicolai, Falk (1993), "Algoritmos de tiempo polinomial para problemas hamiltonianos en grafos hereditarios de distancia bipartitos", Information Processing Letters , 46 (5): 225–230, doi :10.1016/0020-0190(93)90100-N, MR 1228792.
Sachs, Horst (1970), "Sobre la conjetura de Berge relativa a los grafos perfectos", Estructuras combinatorias y sus aplicaciones (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) , Gordon y Breach, págs. 377–384, MR 0272668.
Enlaces externos
"Gráficos hereditarios de distancia", Sistema de Información sobre Clases de Grafos y sus Inclusiones.
