Grafo de intervalos

En teoría de grafos, un grafo de intervalos es el grafo intersección de un multiconjunto de intervalos en la recta real. Cuenta con un vértice para cada intervalo en el conjunto, y una arista entre cada par de vértices correspondientes a los intervalos que se cruzan.

Seven intervals on the real line and the corresponding seven-vertex interval graph.

Definición

Sea {I1, I2, ..., In} ? P(R) un conjunto de intervalos.

El grafo de intervalos correspondiente es G = (V, E), donde

  • V = {I1, I2, ..., In}, y
  • {Ia, Iß} ? E si y solo si Ia n Iß ≠ Ø.

De esta construcción se puede verificar una propiedad común en poder de todos los grafos de intervalos. Es decir, el grafo G es un grafo de intervalos si y solo si los cliques maximales de G pueden ordenarse M1, M2, ..., Mk de tal forma que para cada v ∈ Mi n Mk, donde i < k, es también el caso de que v ∈ Mj para cualquier Mj, i = j = k.[1]

Algoritmos de reconocimiento eficientes

La determinación de si un grafo dado G = (V, E) es un grafo de intervalo se puede hacer en tiempo O(|V|+|E|) mediante la búsqueda de un ordenamiento del clique maximal de G que es consecutiva con respecto a la inclusión de vértice.

El algoritmo de reconocimiento de tiempo lineal original del Booth y Lueker (1976) se basa en su compleja estructura de datos PQ tree, pero Habib et al. (2000) mostró cómo resolver el problema más simplemente usando búsqueda en profundidad lexicográfica, basado en el hecho de que un grafo es un grafo de intervalo si y sólo si es de cuerdas y su complemento es un grafo equivalente.[1][2]

Familias relacionadas de grafos

Grafos de intervalos son grafos de cuerdas y por tanto grafos perfectos.[1][2] Sus complementos pertenecen a la clase de grafos equivalentes,[3] y las relaciones de equivalencia son precisamente las distribuciones de intervalos.[1]

Los grafos de intervalos que tienen una representación de intervalos en el que cada dos intervalos son o disjuntos o anidados son los grafos trivialmente perfectos.

Grafos de intervalos adecuados son grafos de intervalos que tienen una representación de intervalos en el que no hay un intervalo que contiene adecuadamente a cualquier otro intervalo; grafos de intervalos unitarios son los grafos de intervalos que tienen un intervalo de representación en la que cada intervalo tiene una unidad de longitud. Cada grafo de intervalo adecuado es un claw-free graph. Sin embargo, lo contrario no es cierto. Cada claw-free graph no es necesariamente un grafo de intervalo adecuado.[4] Si la colección de segmentos en cuestión es un conjunto, es decir, no se permite repeticiones de segmentos, entonces el grafo es un grafo de intervalo unitario si y solo si es un grafo de intervalo adecuado.[5]

Los grafos de intersección de arcos de un círculo forman grafos de arcos circulares, una clase de grafos que contiene a los grafos de intervalos. Los grafos trapezoidales, intersecciones de trapezoides cuyos lados paralelos se encuentran todos en las mismas dos líneas paralelas, también son una generalización de los grafos de intervalos.

El ancho de camino de un grafo de intervalos es uno menos que el tamaño de clique máximo (o equivalentemente, uno menos que su número cromático), y el ancho de camino de cualquier grafo G es el mismo que el pathwidth más pequeña de un grafo de intervalo que contiene a G como un subgrafo.[6]

Los grafos de intervalos sin triángulos conectados son exactamente los árbol orugas.[7]

Aplicaciones

La teoría matemática de grafos de intervalos se desarrolló con miras a las aplicaciones por investigadores del departamento de matemática de la RAND Corporation's, que incluyó a los jóvenes investigadores como Peter C. Fishburn y estudiantes como Alan C. Tucker y Joel E. Cohen—además de los líderes—como Delbert Fulkerson y (visitante recurrente) Victor Klee.[8] Cohen aplicó grafos de intervalos a modelos matemáticos de población biológica, en concreto red alimentarias.[9]

Otras aplicaciones incluyen la genética, bioinformática, y ciencia de la computación. Encontrar un conjunto de intervalos que representan un grafo de intervalos se puede utilizar también como una forma de montaje de subsecuencias contiguas en mapeo de ADN.[10] Grafos de intervalos son usados para representar problemas de asignación de recursos en investigación de operaciones y teoría de planificación. Cada intervalo representa una solicitud de un recurso por un período específico de tiempo; el problema del conjunto independiente de peso máximo para los grafos representa el problema de encontrar el mejor subconjunto de solicitudes que pueden ser satisfechas sin conflictos.[11] Grafos de intervalos también juegan un papel importante en el razonamiento temporal.[12]

Notas
  1. (Fishburn, 1985)
  2. Golumbic (1980).
  3. Gilmore y Hoffman (1964)
  4. Faudree, Flandrin y Ryjácek (1997), p. 89.
  5. roberts (1969)
  6. Bodlaender (1998).
  7. Eckhoff (1993).
  8. Cohen (1978, pp. ix-10)
  9. Cohen (1978, pp. 12–33)
  10. Zhang et al. (1994).
  11. Bar-Noy et al. (2001).
  12. Golumbic y Shamir (1993).

Referencias

Enlaces externos
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.