Gráfico de intervalo - Interval graph

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 no un vecino del tercero. Un gráfico está libre de AT si no tiene triple asteroide. 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 solo si es cordal y libre de AT.

Otras caracterizaciones:

• Un gráfico es un gráfico de intervalo si y solo si sus camarillas máximas se pueden ordenar de modo que cada vértice que pertenezca a dos de estas camarillas también pertenezca a todas las camarillas entre ellos en el orden. Es decir, para todos con , también es el caso que siempre .${\ Displaystyle M_ {1}, M_ {2}, \ dots, M_ {k}}$${\ Displaystyle v \ en M_ {i} \ cap M_ {k}}$${\ Displaystyle i <k}$${\ Displaystyle v \ en M_ {j}}$${\ Displaystyle i <j <k}$
• Un gráfico es un gráfico de intervalo si y solo si no contiene el gráfico de ciclo como un

${\ Displaystyle C_ {4}}$

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

Algoritmo de reconocimiento eficiente

La determinación de si una gráfica dada es una gráfica de intervalo se puede hacer en el tiempo buscando un orden de las camarillas máximas de que sea consecutiva con respecto a la inclusión de vértices. Muchos de los algoritmos conocidos para este problema funcionan de esta manera, aunque también es posible reconocer gráficos de intervalos en tiempo lineal sin utilizar sus camarillas. ${\ Displaystyle G = (V, E)}$${\ Displaystyle O (| V | + | E |)}$${\ Displaystyle G}$

El algoritmo de reconocimiento de tiempo lineal original de Booth y Lueker (1976) se basa en su compleja estructura de datos de árbol PQ , pero Habib et al. (2000) demostraron cómo resolver el problema de manera más simple utilizando la búsqueda lexicográfica de amplitud primero , basándose en el 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 . Un enfoque similar que utiliza un algoritmo LexBFS de 6 barridos se describe en Corneil, Olariu y Stewart (2009) .

Familias relacionadas de gráficos

Mediante la caracterización de las gráficas de intervalo como gráficas cordales sin AT, las gráficas de intervalo son gráficas fuertemente cordales y, por lo tanto, gráficas perfectas . Sus complementos pertenecen a la clase de gráficos de

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 gráficas de intervalo si y solo si la gráfica es tanto una gráfica dividida como una permutación. gráfico .

Los gráficos de intervalo que tienen una representación de intervalo en la que cada dos intervalos son disjuntos o anidados son los gráficos trivialmente perfectos .

Un gráfico tiene boxicidad como máximo uno si y solo si es un gráfico de intervalo; la boxicidad de un gráfico arbitrario es el número mínimo de gráficos de intervalo en el mismo conjunto de vértices, de modo que la intersección de los conjuntos de bordes de los gráficos de intervalo es . ${\ Displaystyle 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. Los gráficos 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 gráficos de intervalo.

Los gráficos de intervalos sin triángulos conectados son exactamente los árboles de oruga .

Gráficos de intervalos adecuados

Los gráficos de intervalo adecuados son

Un gráfico de intervalo se llama -proper si hay una representación en la que ningún intervalo está contenido por más que otros. Esta noción amplía la idea de gráficos de intervalo adecuados, de modo que un gráfico de intervalo adecuado con 0 es un gráfico de intervalo adecuado. Un gráfico de intervalo se llama -improper si hay una representación en la que ningún intervalo contiene más que otros. Esta noción amplía la idea de gráficos de intervalos adecuados, de modo que un gráfico de intervalos impropios con 0 es un gráfico de intervalos adecuado. Un gráfico de intervalo está anidado si no hay una cadena de longitud de intervalos anidados entre sí. Ésta es una generalización de los gráficos de intervalo adecuados, ya que los gráficos de intervalo anidados 1 son exactamente gráficos de intervalo adecuados. ${\ Displaystyle q}$${\ Displaystyle q}$${\ Displaystyle p}$${\ Displaystyle p}$${\ Displaystyle k}$${\ Displaystyle k + 1}$

Aplicaciones

La teoría matemática de las gráficas de intervalo fue desarrollada con miras a las aplicaciones por parte de investigadores del departamento de matemáticas de RAND Corporation , que incluía 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 intervalo a modelos matemáticos de biología de

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 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 del peso máximo para el gráfico representa el problema de encontrar el mejor subconjunto de solicitudes que se puedan satisfacer sin conflictos. Consulte la programación de intervalos para obtener más información.

Un color de

Otras aplicaciones incluyen genética, bioinformática e 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

Finalizaciones de intervalo y ancho de ruta

Si es un gráfico arbitrario, una

${\ Displaystyle G}$

${\ Displaystyle G}$

${\ Displaystyle G}$

El ancho de

${\ Displaystyle G}$

${\ Displaystyle G}$

Notas

Referencias

enlaces externos

• "gráfico de intervalo" , sistema de información sobre clases de gráficos y sus inclusiones
• Weisstein, Eric W. , "Gráfico de intervalo" , MathWorld