Gráfico cuyos subgrafos inducidos preservan la distancia
Un gráfico distancia-hereditario.
En teoría de grafos , una rama de las matemáticas discretas , un gráfico hereditario de distancias (también llamado gráfico completamente separable ) [1] es un gráfico en el que las distancias en cualquier subgrafo inducido conectado son las mismas que en el gráfico original. Por tanto, cualquier subgrafo inducido hereda las distancias del gráfico más grande.
Los gráficos hereditarios de distancia fueron nombrados y estudiados por primera vez por Howorka (1977), aunque Olaru y Sachs ya demostraron que una clase equivalente de gráficos era perfecta en 1970. [2]
Se sabe desde hace algún tiempo que los gráficos hereditarios de distancia constituyen una clase de gráficos de intersección , [3] pero no se conocía ningún modelo de intersección hasta que Gioan y Paul (2012) proporcionaron uno.
Definición y caracterización
La definición original de un gráfico hereditario de distancia es un gráfico G tal que, si dos vértices u y v pertenecen a un subgrafo inducido conectado 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 es 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 gráficos en los que cada camino inducido es un camino más corto, o de manera equivalente, los gráficos en los que cada camino no más corto tiene al menos un borde que conecta dos vértices de caminos no consecutivos.
Son las gráficas en las que cada ciclo de longitud cinco o más tiene al menos dos diagonales que se cruzan.
Son las gráficas en las que, por 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 las gráficas que no tienen como subgrafías isométricas ningún ciclo de longitud cinco o más, ni ninguna de las otras tres gráficas: una de 5 ciclos con una cuerda, una de 5 ciclos con dos cuerdas que no se cruzan y una de 6 ciclos. con una cuerda que conecta vértices opuestos.
Tres operaciones mediante las cuales se puede construir cualquier gráfico hereditario a distancia.
Son las gráficas que se pueden construir a partir de un solo vértice mediante una secuencia de las siguientes tres operaciones, como se muestra en la ilustración:
Agregue un nuevo vértice colgante conectado por un solo borde a un vértice existente del gráfico.
Reemplaza cualquier vértice del gráfico 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 denominan falsos gemelos entre sí.
Reemplace cualquier vértice del gráfico 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 verdaderos gemelos entre sí.
Son los gráficos que se pueden descomponer completamente en camarillas y estrellas ( gráficos bipartitos completos K 1, q ) mediante una descomposición dividida . En esta descomposición, se encuentra una partición del gráfico en dos subconjuntos, de modo que los bordes que separan los dos subconjuntos forman un subgrafo bipartito completo , forma dos gráficos más pequeños reemplazando cada uno de los dos lados de la partición por un solo vértice, y recursivamente divide estos dos subgrafos. [5]
Son los gráficos que tienen ancho de rango uno, donde el ancho de rango de un gráfico se define como el mínimo, sobre todas las particiones jerárquicas de los vértices del gráfico, del rango máximo entre ciertas submatrices de la matriz de adyacencia del gráfico determinada por la partición. [6]
Cada gráfico hereditario de distancia es un gráfico perfecto , [7] más específicamente un gráfico perfectamente ordenable [8] y un gráfico de Meyniel . Cada gráfico hereditario de distancia es también un gráfico de paridad , un gráfico en el que cada dos caminos inducidos entre el mismo par de vértices tienen una longitud impar o ambos tienen una longitud par. [9] Cada potencia par de un gráfico G hereditario a distancia (es decir, el gráfico G 2 i formado conectando pares de vértices a una distancia máxima de 2 i en G ) es un gráfico cordal . [10]
Cada gráfico hereditario de distancia se puede representar como el gráfico de intersección de cuerdas en un círculo, formando un gráfico circular . Esto se puede ver construyendo el gráfico agregando vértices colgantes, gemelos falsos y gemelos verdaderos, construyendo en cada paso un conjunto correspondiente de cuerdas que representan el gráfico. 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; añadir falsos gemelos corresponde a sustituir 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 pero que son casi paralelas y cruzan el mismo conjunto de otras cuerdas.
Un gráfico hereditario de distancia es bipartito si y solo si no tiene triángulos . Los gráficos bipartitos hereditarios de distancia se pueden construir a partir de un solo vértice agregando 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 gemelo falso preservan la bipartición. Todo grafo bipartito hereditario a distancia es cordal bipartito y modular . [11]
Los gráficos que se pueden construir a partir de un solo vértice mediante vértices colgantes y gemelos verdaderos, sin operaciones de gemelos falsos, son casos especiales de los gráficos ptolemaicos e incluyen los gráficos de bloques . Los gráficos que se pueden construir a partir de un solo vértice mediante operaciones de gemelo falso y gemelo verdadero, sin ningún vértice colgante, son los cografos , que por lo tanto son hereditarios por distancia; los cografos son exactamente las uniones disjuntas de grafos hereditarios de distancia de diámetro 2. La vecindad de cualquier vértice en un gráfico hereditario de distancias es un cografo. El cierre transitivo del gráfico dirigido formado al elegir cualquier conjunto de orientaciones para los bordes de cualquier árbol es hereditario por distancia; el caso especial en el que el árbol está orientado consistentemente lejos de algún vértice forma una subclase de gráficos hereditarios de distancia conocidos como gráficos 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 vértices colgantes y operaciones gemelas, en tiempo lineal. [13]
Debido a que los gráficos hereditarios de distancia son perfectos, algunos problemas de optimización se pueden resolver en tiempo polinomial a pesar de ser NP-difíciles para clases de gráficos más generales. Por lo tanto, es posible en tiempo polinómico encontrar la camarilla máxima o el conjunto independiente máximo en un gráfico hereditario a distancia, o encontrar una coloración gráfica óptima de cualquier gráfico hereditario a distancia. [14]
Debido a que los gráficos hereditarios de distancia son gráficos circulares , heredan algoritmos de tiempo polinomial para gráficos circulares; por ejemplo, es posible determinar en tiempo polinómico el ancho del árbol de cualquier gráfico circular y por tanto de cualquier gráfico hereditario de distancia. [15]
Además, el ancho de camarilla de cualquier gráfico hereditario de distancia es como máximo tres. [16] Como consecuencia, según el teorema de Courcelle , existen algoritmos de programación dinámica eficientes para muchos problemas en estos gráficos. [17]
Varios otros problemas de optimización también se pueden resolver de manera más eficiente utilizando algoritmos diseñados específicamente para gráficos hereditarios de distancia. Como muestran D'Atri y Moscarini (1988), se puede encontrar un conjunto dominante mínimo conectado (o equivalentemente un árbol expansivo con el máximo número posible de hojas) en tiempo polinómico en un gráfico distancia-hereditario. Un ciclo hamiltoniano o una trayectoria hamiltoniana de cualquier gráfico hereditario de distancia también se puede encontrar en tiempo polinómico. [18]
Notas
^ Martillo y Maffray (1990).
^ Olaru y Sachs mostraron la perfección α de las gráficas en las 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 gráficas perfectas.
^ 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 (para gráficos bipartitos de distancia-hereditaria) Hui, Schaefer y Štefankovič (2004).
^ Oum (2005).
^ Howarka (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 bipartitos hereditarios a distancia, Sistema de información sobre clases de gráficos y sus inclusiones, consultado 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) afirmaron un límite de tiempo lineal anterior, pero Damiand descubrió que era erróneo.
^ Cogis y Thierry (2005) presentan un algoritmo directo simple para conjuntos independientes ponderados máximos en gráficos hereditarios de distancia, basado en analizar el gráfico en vértices colgantes y gemelos, corrigiendo un intento previo de tal algoritmo por Hammer y Maffray (1990). Debido a que los gráficos hereditarios de distancia se pueden ordenar perfectamente, se pueden colorear de manera óptima en tiempo lineal usando LexBFS para encontrar un orden perfecto y luego aplicando un algoritmo de coloración codicioso .
^ Kloks (1996); Brandstädt, Le y Spinrad (1999), pág. 170.
^ Golumbic y Róticos (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 , SEÑOR 0859310.
Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Clases de gráficos: una encuesta , Monografías de SIAM sobre aplicaciones y matemáticas discretas, ISBN 0-89871-432-X.
Cogis, O.; Thierry, E. (2005), "Cálculo de conjuntos estables máximos para gráficos 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. 30° Int. Trabajo. Conceptos de teoría de grafos en informática (WG 2004) , Lecture Notes in Computer Science , vol. 3353, Springer-Verlag, págs. 46–57, doi :10.1007/978-3-540-30559-0_4, SEÑOR 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", Teoría de sistemas informáticos , 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 gráficos: aplicación a cografos y gráficos hereditarios de distancia" (PDF) , Ciencias de la Computación Teórica , 263 (1–2): 99–111, doi :10.1016/S0304-3975( 00)00234-6, SEÑOR 1846920.
Espelage, W.; Gurski, F.; Wanke, E. (2001), "Cómo resolver problemas de gráficos NP-difíciles en gráficos acotados por ancho de camarilla en tiempo polinómico", Proc. 27° Int. Trabajo. Conceptos de teoría de grafos en informática (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 gráficos: Caracterizaciones y algoritmos completamente dinámicos para gráficos totalmente descomponibles", Matemáticas Aplicadas Discretas , 160 (6): 708–733, arXiv : 0810.1823 , doi : 10.1016/j. presa.2011.05.007, S2CID 6528410.
Golumbic, Martín Carlos ; Rotics, Udi (2000), "Sobre el ancho de camarilla de algunas clases de gráficos perfectos", Revista Internacional de Fundamentos de Ciencias de la Computación , 11 (3): 423–443, doi :10.1142/S0129054100000260, MR 1792124.
Howorka, Edward (1977), "Una caracterización de gráficos 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 gráficos hereditarios a distancia", Computación y combinatoria: octava conferencia internacional anual, COCOON 2002 Singapur, 15 al 17 de agosto de 2002, Actas , Apuntes de conferencias en informática , vol. 2387, Springer-Verlag, págs. 51–75, doi :10.1007/3-540-45655-4_10, ISBN 978-3-540-43996-7, señor 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", Matemáticas discretas , 2 (3): 253–267, doi : 10.1016/0012-365X(72)90006-4 , SEÑOR 0302480.
McKee, Terry A.; McMorris, FR (1999), Temas de teoría de grafos de intersección , Monografías de 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, señor 1672910
Müller, Haiko; Nicolai, Falk (1993), "Algoritmos de tiempo polinómico para problemas hamiltonianos en gráficos hereditarios de distancia bipartitos", Cartas de procesamiento de información , 46 (5): 225–230, doi :10.1016/0020-0190(93)90100-N, SEÑOR 1228792.
Sachs, Horst (1970), "Sobre la conjetura de Berge sobre los gráficos 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 distancia-hereditarios", Sistema de Información sobre Clases de Grafos y sus Inclusiones.
