En la teoría de grafos , una rama de las matemáticas discretas , un grafo hereditario de distancia (también llamado grafo completamente separable ) [1] es un grafo en el que las distancias en cualquier subgrafo inducido conectado son las mismas que en el grafo original. Por lo tanto, cualquier subgrafo inducido hereda las distancias del gráfico más grande.
Los gráficos de distancia hereditaria 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) dieron uno .
Definición y caracterización
La definición original de un gráfico de la distancia-hereditario es un gráfico G tal que, si cualquiera de los dos vértices u y v pertenecen a un subgrafo inducido conectado H de G , entonces algún camino más corto de conexión 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 de distancia hereditaria 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 equivalentemente los gráficos en los que cada camino no más corto tiene al menos un borde que conecta dos vértices de camino no consecutivos.
- Son los gráficos en los que cada ciclo de cinco o más de longitud tiene al menos dos diagonales cruzadas.
- 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 subgráficas isométricas ningún ciclo de cinco o más de longitud, ni ninguna de las otras tres gráficas: una de 5 ciclos con una cuerda, una de 5 ciclos con dos cuerdas no cruzadas y una de 6 ciclos. con un acorde que conecta vértices opuestos.
- Son los gráficos 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í.
- Reemplaza 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 subgráfico bipartito completo , forman 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 particiona estos dos subgrafos. [5]
- Son los gráficos que tienen rango de ancho uno, donde el rango de ancho 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]
- Son los gráficos libres de HHDG, lo que significa que tienen una caracterización gráfica prohibida según la cual ningún subgrafo inducido puede ser una casa (el gráfico de complemento de un gráfico de trayectoria de cinco vértices ), un agujero (un gráfico de ciclo de cinco o más vértices) , dominó (ciclo de seis vértices más un borde diagonal entre dos vértices opuestos), o gema (ciclo de cinco vértices más dos diagonales incidentes al mismo vértice).
Relación con otras familias de gráficos
Cada gráfico de distancia-hereditario 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 ambos una longitud impar o ambos tienen una longitud par. [9] Cada potencia par de un gráfico G hereditario de distancia (es decir, el gráfico G 2 i formado al conectar pares de vértices a una distancia como máximo 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, en cada paso construyendo un conjunto correspondiente de acordes que representan el gráfico. Agregar un vértice colgante corresponde a agregar un acorde cerca de los puntos finales de un acorde existente para que cruce solo ese acorde; agregar gemelos falsos corresponde a reemplazar un acorde por dos acordes paralelos que cruzan el mismo conjunto de otros acordes; y agregar gemelos verdaderos corresponde a reemplazar un acorde por dos acordes que se cruzan pero son casi paralelos y cruzan el mismo conjunto de otros acordes.
Un gráfico hereditario de distancia es bipartito si y solo si no tiene triángulos . Los gráficos bipartitos de distancia hereditaria se pueden construir a partir de un único 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 conservan la bipartita. Cada grafo hereditario de distancia bipartito es bipartito cordal y modular . [11]
Los gráficos que se pueden construir a partir de un único 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 bloque . Las gráficas que se pueden construir a partir de un solo vértice mediante operaciones de falso gemelo y gemelo verdadero, sin vértices pendientes, son las cografías , por lo que son hereditarias a distancia; las cografías son exactamente las uniones disjuntas de las gráficas hereditarias de distancia de diámetro 2. La vecindad de cualquier vértice en una gráfica hereditaria a distancia es una cografía. 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 grafos hereditarios de distancia conocidos como grafos trivialmente perfectos , que también se denominan cografos cordales. [12]
Algoritmos
Los gráficos de distancia hereditaria se pueden reconocer y analizar en una secuencia de vértices pendientes y operaciones gemelas, en tiempo lineal. [13]
Debido a que los gráficos de distancia hereditaria son perfectos, algunos problemas de optimización se pueden resolver en tiempo polinomial para ellos a pesar de ser NP-difícil para clases de gráficos más generales. Por lo tanto, en el tiempo polinomial es posible encontrar la camarilla máxima o el conjunto independiente máximo en un gráfico hereditario de distancia, o encontrar un color de gráfico óptimo de cualquier gráfico hereditario de 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 polinomial el ancho de árbol de cualquier gráfico circular y, por lo 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) , un conjunto dominante conectado mínimo (o equivalentemente un árbol de expansión con el número máximo posible de hojas) se puede encontrar en tiempo polinomial en un gráfico de distancia-hereditario. Un ciclo hamiltoniano o una trayectoria hamiltoniana de cualquier gráfico hereditario de distancia también se puede encontrar en tiempo polinomial. [18]
Notas
- ^ Hammer y Maffray (1990) .
- ↑ Olaru y Sachs mostraron la perfección α de los gráficos en los que cada ciclo de cinco o más de longitud tiene un par de diagonales cruzadas ( Sachs 1970 , Teorema 5). Según Lovász (1972) , α-perfección es una forma equivalente de definición de gráficos perfectos.
- ^ McKee y McMorris (1999)
- ^ Howorka (1977) ; Bandelt y Mulder (1986) ; Hammer y Maffray (1990) ; Brandstädt, Le y Spinrad (1999) , Teorema 10.1.1, pág. 147.
- ^ Gioan y Paul (2012) . Una descomposición estrechamente relacionado fue utilizado para el delineado de gráfico por Eppstein, Goodrich y Meng (2006) y (para grafos bipartitos distancia hereditaria) por Hui, Schaefer y Štefankovič (2004) .
- ^ Oum (2005) .
- ^ Howorka (1977) .
- ^ Brandstädt, Le & Spinrad (1999) , págs. 70-71 y 82.
- ^ Brandstädt, Le y Spinrad (1999) , p.45.
- ^ Brandstädt, Le y 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, consultado el 30 de septiembre de 2016.
- ^ Cornelsen y Di Stefano (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 Hammer y Maffray (1990) en tal algoritmo. Debido a que los gráficos de distancia hereditaria se puedenordenarperfectamente, se pueden colorear de manera óptima en tiempo lineal utilizando LexBFS para encontrar un orden perfecto y luego aplicando unalgoritmo de coloración codicioso .
- ^ 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 a 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), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
- Cogis, O .; Thierry, E. (2005), "Computación de conjuntos estables máximos para gráficos de distancia-hereditarios", 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 arborescentes: caracterización, reconocimiento y aplicaciones", Proc. 30th Int. Worksh. Conceptos teóricos de gráficos en ciencias de la computación (WG 2004) , Lecture Notes in Computer Science , 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 con solución de tiempo lineal en gráficos de ancho de camarilla acotado", Teoría de los sistemas informáticos , 33 (2): 125-150, doi : 10.1007 / s002249910009.
- D'Atri, Alessandro; Moscarini, Marina (1988), "Gráficos hereditarios a 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 cografías y gráficos hereditarios a distancia" (PDF) , Theoretical Computer Science , 263 (1-2): 99-111, doi : 10.1016 / S0304-3975 ( 00) 00234-6 , MR 1846920.
- Eppstein, David ; Goodrich, Michael T .; Meng, Jeremy Yu (2006), "Dibujos confluentes delta", en Healy, Patrick; Nikolov, Nikola S. (eds.), Proc. 13 ° Int. Symp. Graph Drawing (GD 2005) , Lecture Notes in Computer Science , 3843 , Springer-Verlag, págs. 165-176, arXiv : cs.CG/0510024 , doi : 10.1007 / 11618058_16 , MR 2244510.
- Espelage, W .; Gurski, F .; Wanke, E. (2001), "Cómo resolver problemas de gráficos NP-duros en gráficos acotados de ancho de camarilla en tiempo polinomial", Proc. 27th Int. Worksh. Conceptos teóricos de gráficos en informática (WG 2001) , Lecture Notes in Computer Science , 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", Discrete Applied Mathematics , 160 (6): 708–733, arXiv : 0810.1823 , doi : 10.1016 / j. presa.2011.05.007.
- Golumbic, Martin Charles ; Rotics, Udi (2000), "On the clique-width of some perfect graph classes", International Journal of Foundations of Computer Science , 11 (3): 423–443, doi : 10.1142 / S0129054100000260 , MR 1792124.
- Hammer, Peter Ladislaw ; Maffray, Frédéric (1990), "Gráficos completamente separables", Matemáticas aplicadas discretas , 27 (1–2): 85–99, doi : 10.1016 / 0166-218X (90) 90131-U , MR 1055593.
- Howorka, Edward (1977), "Una caracterización de gráficos hereditarios a distancia", The Quarterly Journal of Mathematics , Second Series, 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 de distancia", Computación y combinatoria: 8a Conferencia Internacional Anual, COCOON 2002 Singapur, 15-17 de agosto de 2002, Actas , Notas de conferencias en Ciencias de la Computación , 2387 , Springer-Verlag, págs. 51–75, doi : 10.1007 / 3-540-45655-4_10 , ISBN 978-3-540-43996-7, MR 2064504.
- Hui, Peter; Schaefer, Marcus; Štefankovič, Daniel (2004), "Vías de tren y dibujos confluentes", en Pach, János (ed.), Proc. 12th Int. Symp. Graph Drawing (GD 2004) , Lecture Notes in Computer Science , 3383 , Springer-Verlag, págs. 318–328.
- Kloks, T. (1996), "Treewidth of circle graphs", International Journal of Foundations of Computer Science , 7 (2): 111-120, doi : 10.1142 / S0129054196000099.
- Lovász, László (1972), "Hipergrafías normales y la conjetura de la gráfica perfecta", Matemáticas discretas , 2 (3): 253-267, doi : 10.1016 / 0012-365X (72) 90006-4 , MR 0302480.
- McKee, Terry A .; McMorris, FR (1999), Temas de la teoría de grafos de intersección , Monografías de SIAM sobre matemáticas y aplicaciones discretas, 2 , Filadelfia: Sociedad de matemáticas industriales y aplicadas, doi : 10.1137 / 1.9780898719802 , ISBN 0-89871-430-3, MR 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.
- Oum, Sang-il (2005), "Rank-width and vertex-minors", Journal of Combinatorial Theory , Serie B, 95 (1): 79–100, doi : 10.1016 / j.jctb.2005.03.003 , MR 2156341.
- Sachs, Horst (1970), "Sobre la conjetura de Berge sobre 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 hereditarios a distancia" , Sistema de información sobre clases de gráficos y sus inclusiones.