Gráfica de intervalos

Un gráfico de intervalos  es un gráfico de intersecciones de un conjunto múltiple de intervalos en una línea. Tiene un vértice para cada intervalo del conjunto y una arista entre cada par de vértices si los intervalos correspondientes se intersecan.

Definición

Sea  un conjunto de intervalos.

El gráfico de intervalo correspondiente es , donde

A partir de esta construcción se pueden obtener propiedades generales de los gráficos de intervalos. Por lo tanto, el grafo G es un intervalo si y solo si las camarillas más grandes del grafo G pueden ordenarse de tal manera que para cualquier , donde , también se cumple para cualquier [1] .

Algoritmos de reconocimiento eficientes

Es posible determinar si un grafo es un grafo de intervalos en el tiempo ordenando las camarillas más grandes del grafo G .

El algoritmo de reconocimiento de tiempo lineal original de Booth y Lueker ( Booth, Lueker 1976 ) se basa en una estructura compleja de árboles PQ , pero Habib, McConnell, Paul y Viennot ( Habib, McConnell, Paul, Viennot 2000 ) mostraron cómo resolver el problema de forma más sencilla utilizando la búsqueda lexicográfica en amplitud y basada en el hecho de que un grafo es intervalo si y solo si es cordal y su complemento  es un grafo de comparabilidad [1] [2] .

Familias de grafos relacionadas

Los gráficos de intervalo son cordales y, por lo tanto, perfectos [1] [2] . Sus complementos pertenecen a la clase de gráficos de comparabilidad [3] , y la relación de comparación es exactamente el orden del intervalo [1] .

Un gráfico de intervalos que tiene una representación de intervalos en la que dos intervalos cualesquiera son disjuntos o anidados son gráficos perfectos triviales .

Un gráfico de intervalo regular  es un gráfico de intervalo que tiene una representación de intervalo en la que ningún intervalo es un subconjunto propio de ningún otro intervalo. Los gráficos de intervalos unitarios  son gráficos de intervalos que tienen una representación de intervalos en la que cada intervalo tiene una longitud unitaria. Cualquier gráfico de intervalo regular no tiene garras . Sin embargo, lo contrario no es cierto: un gráfico sin garras no es necesariamente un gráfico de intervalo regular [4] . Si el conjunto de segmentos es un conjunto , es decir, no se permite la repetición de segmentos, entonces el gráfico es un gráfico de intervalo unitario si y solo si es un gráfico de intervalo regular [5] .

Los gráficos de intersección de arco circular forman gráficos de arco circular , una clase de gráficos que contienen gráficos de intervalo. Los gráficos trapezoidales , la intersección de trapecios cuyos lados paralelos se encuentran en dos líneas paralelas, son una generalización de los gráficos de intervalo.

El ancho de ruta de un gráfico de intervalo es uno menos que el tamaño de la camarilla máxima (o, de manera equivalente, uno menos que su número cromático), y el ancho de ruta de cualquier gráfico G es igual al ancho de ruta más pequeño de un gráfico de intervalo que contiene G como un subgrafo [6] .

Los gráficos de intervalos relacionados sin triángulos  son exactamente árboles de oruga [7] .

Gráfico de intervalo aleatorio : un gráfico de intervalo construido sobre una familia aleatoria de segmentos, por ejemplo, los segmentos de los vértices de los segmentos se pueden elegir, por ejemplo, por distribución natural en un segmento unitario.

Aplicaciones

La teoría matemática de los gráficos de intervalos se desarrolló teniendo en cuenta las aplicaciones de los investigadores de la división de matemáticas de RAND Corporation , que incluía a jóvenes investigadores como Peter Fishburne y estudiantes como Alan Tucker y Joel Coen , no contando con líderes como Delbert Ray Fulkerson y (invitado frecuente) Victor Klee [8] . Cohen ha aplicado gráficos de intervalos a modelos matemáticos de poblaciones , especialmente cadenas alimentarias [9] .

Otras aplicaciones incluyen la genética, la bioinformática y la informática . La búsqueda de un conjunto de segmentos que representan un gráfico de intervalo puede utilizarse como técnica para ensamblar secuencias continuas en el ADN [10] . Los gráficos de intervalo se utilizan para establecer problemas de asignación de recursos en la investigación de operaciones y la programación de tareas . Cada brecha representa una solicitud de un recurso para un período de tiempo específico. El problema de encontrar un conjunto independiente del peso máximo de un gráfico es el problema de encontrar el mejor subconjunto de consultas que se pueden ejecutar sin conflictos [11] .

Notas

  1. ↑ 1 2 3 4 Fishburn, 1985 .
  2. ↑ 12 Golumbic , 1980 .
  3. ↑ Gilmore, Hoffman, 1964 .
  4. ↑ Faudree, Flandrin, Ryjáček, 1997 , p. 89
  5. ↑ Roberts, 1969 .
  6. ↑ Bodlaender, 1998 .
  7. ↑ Eckoff, 1993 .
  8. ↑ Cohen, 1978 ix-10
  9. ↑ Cohen, 1978 12-33
  10. ↑ Zhang et al., 1994 .
  11. ↑ Bar-Noy, Bar-Yehuda, Freund, Naor, 2001 .

Literatura

Enlaces