stringtranslate.com

Gráfica de distancia-herencia

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 grafos 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 grafos 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]

Tres operaciones mediante las cuales se puede construir cualquier grafo hereditario de distancia.

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 conectado 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

  1. ^ Martillo y Maffray (1990).
  2. ^ 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.
  3. ^ McKee y McMorris (1999)
  4. ^ Howarka (1977); Bandelt y Mulder (1986); Martillo y Maffray (1990); Brandstädt, Le y Spinrad (1999), Teorema 10.1.1, pág. 147.
  5. ^ 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) (para gráficos hereditarios de distancia bipartitos).
  6. ^ Oum (2005).
  7. ^ Howorka (1977).
  8. ^ Brandstädt, Le y Spinrad (1999), págs. 70–71 y 82.
  9. ^ Brandstädt, Le y Spinrad (1999), p.45.
  10. ^ Brandstädt, Le & Spinrad (1999), Teorema 10.6.14, p.164.
  11. ^ 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.
  12. ^ Cornelsen y Di Stéfano (2005).
  13. ^ 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.
  14. ^ Cogis y Thierry (2005) presentan un algoritmo directo simple para conjuntos independientes de ponderación máxima 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 .
  15. ^ Kloks (1996); Brandstädt, Le y Spinrad (1999), pág. 170.
  16. ^ Golumbic y Rotics (2000).
  17. ^ Courcelle, Makowski y Rotics (2000); Espelage, Gurski y Wanke (2001).
  18. ^ Hsieh y col. (2002); Müller y Nicolai (1993).

Referencias

Enlaces externos