Gráfico de intervalos

En teoría de grafos, un gráfico de intervalos es un gráfico no dirigido formado a partir de un conjunto de intervalos en la recta real, con un vértice para cada intervalo y una arista entre los vértices cuyos intervalos se cruzan. Es la gráfica de intersección de los intervalos.

Las gráficas de intervalos son gráficas cordales y gráficas perfectas. Se pueden reconocer en tiempo lineal, y se puede encontrar una coloración de gráfico óptima o una camarilla máxima en estos gráficos en tiempo lineal. Los gráficos de intervalos incluyen todos los gráficos de intervalos propios, gráficos definidos de la misma manera a partir de un conjunto de intervalos unitarios.

Estos gráficos se han utilizado para modelar redes alimentarias y para estudiar problemas de programación en los que se debe seleccionar un subconjunto de tareas que se realizarán en momentos que no se superpongan. Otras aplicaciones incluyen el ensamblaje de subsecuencias contiguas en el mapeo de ADN y el razonamiento temporal.

Definición

An interval graph is an undirected graph G formed from a family of intervals

Si,i=0,1,2,...... {displaystyle S_{i},quad i=0,1,2, dots }

creando un vértice v_i para cada intervalo S_i, y conectando dos vértices v_i y v_j por un borde siempre que el correspondiente dos conjuntos tienen una intersección no vacía. Es decir, el conjunto de bordes de G es

E()G)={}()vi,vj)▪ ▪ Si∩ ∩ Sjل ل ∅ ∅ }.{displaystyle E(G)={i},v_{j}mid S_{i}cap S_{j}neq emptyset }

Es la gráfica de intersección de los intervalos.

Caracterizaciones

Tres vértices forman un triple asteroide (AT) en un gráfico si, para cada dos, existe un camino que contiene esos dos pero ningún vecino del tercero. Un gráfico está libre de AT si no tiene un triple asteroidal. La caracterización más temprana de los gráficos de intervalo parece ser la siguiente:

• Un gráfico es un gráfico de intervalo si y sólo si es coral y sin AT.

Otras caracterizaciones:

• Un gráfico es un gráfico de intervalo si y sólo si sus camarillas máximas se pueden ordenar M1,M2,...... ,Mk{displaystyle M_{1},M_{2},dots M_{k} tal que cada vértice que pertenece a dos de estas camarillas también pertenece a todas las camarillas entre ellas en el orden. Eso es, para todos v▪ ▪ Mi∩ ∩ Mk{displaystyle vin M_{i}cap M_{k} con <math alttext="{displaystyle ii.k{displaystyle i wonK}<img alt="{displaystyle i, es también el caso de que v▪ ▪ Mj{displaystyle vin M_{j} siempre <math alttext="{displaystyle i<ji.j.k{displaystyle i hicieran referencias<img alt="{displaystyle i<j.
• Un gráfico es un gráfico de intervalo si y sólo si no contiene el gráfico del ciclo C4{displaystyle C_{4} como subgrafo inducido y es el complemento de un gráfico de comparabilidad.

Se han descrito varias otras caracterizaciones de gráficos de intervalos y variantes.

Algoritmo de reconocimiento eficiente

Determinar si un gráfico dado G=()V,E){displaystyle G=(V,E)} es un gráfico de intervalo se puede hacer en O()SilencioVSilencio+SilencioESilencio){displaystyle O(vivienda) tiempo buscando un pedido de las camarillas máximas de G{displaystyle G. eso es consecutivo con respecto a la inclusión del vértice. Muchos de los algoritmos conocidos para este problema funcionan de esta manera, aunque también es posible reconocer gráficos de intervalo en tiempo lineal sin utilizar sus camarillas.

El algoritmo de reconocimiento de tiempo lineal original de Booth & Lueker (1976) se basa en su compleja estructura de datos de árbol PQ, pero Habib et al. (2000) mostraron cómo resolver el problema de manera más simple usando una búsqueda lexicográfica de amplitud primero, basándose en el hecho de que un gráfico es un gráfico de intervalo si y solo si es cordal y su complemento es un gráfico de comparabilidad. Un enfoque similar que utiliza un algoritmo LexBFS de 6 barridos se describe en Corneil, Olariu & Estuardo (2009).

Familias de gráficos relacionadas

Por la caracterización de los gráficos de intervalo como gráficos cordales sin AT, los gráficos de intervalo son gráficos fuertemente cordales y, por lo tanto, gráficos perfectos. Sus complementos pertenecen a la clase de gráficos de comparabilidad, y las relaciones de comparabilidad son precisamente los órdenes de intervalo.

Del hecho de que una gráfica es una gráfica de intervalo si y solo si es cordal y su complemento es una gráfica de comparabilidad, se deduce que la gráfica y su complemento son ambas gráficas de intervalo si y solo si la gráfica es una gráfica dividida y un gráfico de permutación.

Las gráficas de intervalo que tienen una representación de intervalo en la que cada dos intervalos son disjuntos o anidados son gráficas trivialmente perfectas.

Un gráfico tiene boxicidad a la mayoría si y sólo si es un gráfico de intervalo; la boxicidad de un gráfico arbitrario G{displaystyle G. es el número mínimo de gráficos de intervalo en el mismo conjunto de vértices tal que la intersección de los bordes conjuntos de los gráficos de intervalo es G{displaystyle G..

Las gráficas de intersección de arcos de un círculo forman gráficas de arco circular, una clase de gráficas que contiene las gráficas de intervalo. Las gráficas de trapecio, intersecciones de trapecios cuyos lados paralelos se encuentran en las mismas dos líneas paralelas, también son una generalización de las gráficas de intervalo.

Los gráficos de intervalos libres de triángulos conectados son exactamente los árboles de orugas.

Gráficos de intervalos adecuados

Los gráficos de intervalos adecuados son gráficos de intervalos que tienen una representación de intervalo en la que ningún intervalo contiene adecuadamente ningún otro intervalo; Los gráficos de intervalos unitarios son gráficos de intervalos que tienen una representación de intervalo en la que cada intervalo tiene una longitud unitaria. Una representación de intervalo unitario sin intervalos repetidos es necesariamente una representación de intervalo adecuada. No toda representación de intervalo adecuada es una representación de intervalo unitario, pero todo gráfico de intervalo adecuado es un gráfico de intervalo unitario, y viceversa. Todo gráfico de intervalo adecuado es un gráfico sin garras; por el contrario, las gráficas de intervalo adecuadas son exactamente las gráficas de intervalo sin garras. Sin embargo, existen gráficos sin garras que no son gráficos de intervalos.

Un gráfico de intervalo se llama q{displaystyle q}-proper si hay una representación en la que no hay intervalo que contenga más que q{displaystyle q} otros. Esta noción extiende la idea de gráficos de intervalo adecuado de tal manera que un gráfico de intervalo 0-proper es un gráfico de intervalo adecuado. Un gráfico de intervalo se llama p{displaystyle p}-improper si hay una representación en la que ningún intervalo contiene más que p{displaystyle p} otros. Esta noción extiende la idea de gráficos de intervalo adecuado de tal manera que un gráfico de intervalo 0-improper es un gráfico de intervalo adecuado. Un gráfico de intervalo es k{displaystyle k}-sonado si no hay cadena de longitud k+1{displaystyle k+1} de intervalos anidados entre sí. Esta es una generalización de gráficos de intervalo adecuado ya que gráficos de intervalo de 1-pernotado son exactamente gráficos de intervalo adecuado.

Aplicaciones

La teoría matemática de los gráficos de intervalos fue desarrollada con miras a sus aplicaciones por parte de investigadores del departamento de matemáticas de RAND Corporation, que incluía investigadores jóvenes, como Peter C. Fishburn y estudiantes como Alan C. Tucker y Joel E. Cohen, además de líderes como Delbert Fulkerson y (visitante recurrente) Victor Klee. Cohen aplicó gráficos de intervalos a modelos matemáticos de biología de poblaciones, específicamente a redes alimentarias.

Los gráficos de intervalos se utilizan para representar problemas de asignación de recursos en la investigación de operaciones y la teoría de la programación. En estas aplicaciones, cada intervalo representa una solicitud de un recurso (como una unidad de procesamiento de un sistema informático distribuido o una sala para una clase) durante un período de tiempo específico. El problema del conjunto independiente de peso máximo para el gráfico representa el problema de encontrar el mejor subconjunto de solicitudes que puedan satisfacerse sin conflictos. Consulte programación de intervalos para obtener más información.

Una coloración óptima del gráfico de intervalo representa una asignación de recursos que cubre todas las solicitudes con la menor cantidad de recursos posible; se puede encontrar en tiempo polinómico mediante un algoritmo de coloración codicioso que colorea los intervalos en orden según sus extremos izquierdos.

Otras aplicaciones incluyen la genética, la bioinformática y la informática. Encontrar un conjunto de intervalos que representen un gráfico de intervalos también se puede utilizar como una forma de ensamblar subsecuencias contiguas en el mapeo de ADN. Los gráficos de intervalos también juegan un papel importante en el razonamiento temporal.

Finalización de intervalos y ancho de ruta

Si G{displaystyle G. es un gráfico arbitrario, un intervalo de finalización de G{displaystyle G. es un gráfico de intervalo en el mismo conjunto de vértice que contiene G{displaystyle G. como subgrafo. La versión parametrizada de la terminación del intervalo (encontrar un supergraph de intervalo con k los bordes adicionales) es fijo parámetro tractable, y además, es solvable en tiempo subexponencial parametrado.

El ancho de camino de un gráfico de intervalo es uno menos que el tamaño de su camara máxima (o equivalente, uno menos que su número cromático), y el ancho de ruta de cualquier gráfico G{displaystyle G. es el mismo que el más pequeño recorrido de un gráfico de intervalo que contiene G{displaystyle G. como subgrafo.

Enumeración combinatoria

El número de gráficos de intervalos conectados en n{displaystyle n} vértices sin etiqueta, para n=1,2,3,...... {displaystyle n=1,2,3,dots}, es:

1, 1, 2, 5, 15, 56, 250, 1328, 8069, 54962, 410330, 3317302,... A005976 en el OEIS)

Sin la asunción de conectividad, los números son mayores. Número de gráficos de intervalo en n{displaystyle n} vértices sin etiquetar, no necesariamente conectados, es:

1, 2, 4, 10, 27, 92, 369, 1807, 10344, 67659, 491347, 3894446,... (secuencia) A005975 en el OEIS)

Estos números muestran un crecimiento más rápido que exponencial: el número de gráficos de intervalo en 3n{displaystyle 3n} vertices sin etiqueta es al menos n!/33n{displaystyle ¡No!. Debido a esta tasa de crecimiento rápido, los gráficos de intervalo no han atado el ancho gemelo.