Gráfica de intervalo

Gráfica de intersección de intervalos en la recta de números reales

Siete intervalos en la línea real y el gráfico de intervalo de siete vértices correspondiente.

En teoría de grafos , un grafo de intervalos es un grafo 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 intersecan. Es el grafo de intersección de los intervalos.

Los grafos de intervalos son grafos cordales y grafos perfectos . Se pueden reconocer en tiempo lineal , y se puede encontrar una coloración de grafo óptima o una camarilla máxima en estos grafos en tiempo lineal. Los grafos de intervalos incluyen todos los grafos de intervalos propios , grafos 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 superponen. Otras aplicaciones incluyen el ensamblaje de subsecuencias contiguas en el mapeo de ADN y el razonamiento temporal.

Definición

Un gráfico de intervalo es un gráfico no dirigido G formado a partir de una familia de intervalos.

${\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 mediante una arista siempre que los dos conjuntos correspondientes tengan una intersección no vacía. Es decir, el conjunto de aristas de G es

${\displaystyle E(G)=\{(v_{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 independientes forman una tripleta asteroidal (AT) en un grafo si, para cada dos, existe un camino que los contiene pero no un vecino del tercero. Un grafo no tiene AT si no tiene tripleta asteroidal. La caracterización más temprana de los grafos de intervalo parece ser la siguiente:

• Un gráfico es un gráfico de intervalo si y sólo si es cordal y libre de AT. ^[1]

Otras caracterizaciones:

• Un grafo es un grafo de intervalo si y solo si sus camarillas máximas pueden ordenarse de tal manera que cada vértice que pertenece a dos de estas camarillas también pertenece a todas las camarillas entre ellas en el ordenamiento. Es decir, para cada con , también es el caso que siempre que . ^[2] ${\displaystyle M_{1},M_{2},\dots ,M_{k}}$ ${\displaystyle v\in M_{i}\cap M_{k}}$ ${\displaystyle i<k}$ ${\displaystyle v\in M_{j}}$ ${\displaystyle i<j<k}$
• Un gráfico es un gráfico de intervalo si y sólo si no contiene el gráfico de ciclo como subgráfico inducido y es el complemento de un gráfico de comparabilidad . ^[3] ${\displaystyle C_{4}}$

Se han descrito otras caracterizaciones de gráficos de intervalos y variantes. ^[4]

Algoritmo de reconocimiento eficiente

Para determinar si un grafo dado es un grafo de intervalos se puede buscar en el tiempo un orden de los grupos máximos de que sean consecutivos 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 grafos de intervalos en tiempo lineal sin utilizar sus grupos. ^[5] ${\displaystyle G=(V,E)}$ ${\displaystyle O(|V|+|E|)}$ ${\displaystyle G}$

El algoritmo original de reconocimiento de tiempo lineal de Booth y 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 utilizando la búsqueda en amplitud lexicográfica , 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 . ^[6] Un enfoque similar que utiliza un algoritmo LexBFS de 6 barridos se describe en Corneil, Olariu y Stewart (2009).

Familias de gráficos relacionadas

Mediante la caracterización de los grafos de intervalo como grafos cordales libres de AT, ^[1] los grafos de intervalo son grafos fuertemente cordales y por lo tanto grafos perfectos . Sus complementos pertenecen a la clase de grafos de comparabilidad , ^[3] y las relaciones de comparabilidad son precisamente los órdenes de intervalo . ^[7]

Del hecho de que un grafo es un grafo de intervalo si y solo si es cordal y su complemento es un grafo de comparabilidad , se deduce que el grafo y su complemento son ambos grafos de intervalo si y solo si el grafo es a la vez un grafo dividido y un grafo de permutación .

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 grafo tiene boxicidad como máximo uno si y solo si es un grafo de intervalo; la boxicidad de un grafo arbitrario es el número mínimo de grafos de intervalo en el mismo conjunto de vértices tales que la intersección de los conjuntos de aristas de los grafos de intervalo sea . ${\displaystyle G}$ ${\displaystyle G}$

Los gráficos de intersección de arcos de un círculo forman gráficos de arco circular , una clase de gráficos que contiene los gráficos de intervalo. Los gráficos trapezoidales , intersecciones de trapecios cuyos lados paralelos se encuentran todos sobre las mismas dos líneas paralelas, también son una generalización de los gráficos de intervalo.

Los gráficos de intervalos libres de triángulos conectados son exactamente los árboles de oruga . ^[8]

Gráficas de intervalos propios

Los grafos de intervalos propios son grafos de intervalos que tienen una representación de intervalos en la que ningún intervalo contiene propiamente a ningún otro intervalo; los grafos de intervalos unitarios son los grafos de intervalos que tienen una representación de intervalos en la que cada intervalo tiene una longitud unitaria. Una representación de intervalos unitarios sin intervalos repetidos es necesariamente una representación de intervalos propios. No toda representación de intervalos propios es una representación de intervalos unitarios, pero todo grafo de intervalos propios es un grafo de intervalos unitarios, y viceversa. ^[9] Todo grafo de intervalos propios es un grafo sin garras ; por el contrario, los grafos de intervalos propios son exactamente los grafos de intervalos sin garras. Sin embargo, existen grafos sin garras que no son grafos de intervalos. ^[10]

Un grafo de intervalo se llama -propio si hay una representación en la que ningún intervalo está contenido por más que otros. Esta noción extiende la idea de grafos de intervalo propios de tal manera que un grafo de intervalo 0-propio es un grafo de intervalo propio. ^[11] Un grafo de intervalo se llama -impropio si hay una representación en la que ningún intervalo contiene más que otros. Esta noción extiende la idea de grafos de intervalo propios de tal manera que un grafo de intervalo 0-impropio es un grafo de intervalo propio. ^[12] Un grafo de intervalo está -anidado si no hay una cadena de longitud de intervalos anidados entre sí. Esta es una generalización de grafos de intervalo propios ya que los grafos de intervalo 1-anidados son exactamente grafos de intervalo propios. ^[13] ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle k+1}$

Aplicaciones

La teoría matemática de los gráficos de intervalos fue desarrollada con vistas a su aplicación por investigadores del departamento de matemáticas de la Corporación RAND , 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 . ^[14] Cohen aplicó los gráficos de intervalos a modelos matemáticos de biología de poblaciones , específicamente redes alimentarias . ^[15]

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

Una coloración óptima del gráfico de intervalos representa una asignación de recursos que cubre todas las solicitudes con la menor cantidad de recursos posible; se puede encontrar en tiempo polinomial mediante un algoritmo de coloración codicioso que colorea los intervalos en orden ordenado por sus puntos finales izquierdos. ^[17]

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 . ^[18] Los gráficos de intervalos también juegan un papel importante en el razonamiento temporal. ^[19]

Intervalos de finalización y ancho de ruta

Si es un gráfico arbitrario, una compleción de intervalo de es un gráfico de intervalo en el mismo conjunto de vértices que contiene como un subgráfico. La versión parametrizada de compleción de intervalo (encontrar un supergráfico de intervalo con k aristas adicionales) es manejable con parámetros fijos y, además, es solucionable en tiempo subexponencial parametrizado. ^{[20] [21]} ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

El ancho de ruta de un gráfico de intervalo es uno menos que el tamaño de su grupo máximo (o equivalentemente, uno menos que su número cromático), y el ancho de ruta de cualquier gráfico es el mismo que el ancho de ruta más pequeño de un gráfico de intervalo que contiene un subgráfico. ^[22] ${\displaystyle G}$ ${\displaystyle G}$

Enumeración combinatoria

El número de gráficos de intervalos conectados en vértices no etiquetados, para , es: ^[23] ${\displaystyle n}$ ${\displaystyle n=1,2,3,\dots }$

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

Sin el supuesto de conectividad, los números son mayores. El número de grafos de intervalos en vértices no etiquetados, no necesariamente conectados, es: ^[24] ${\displaystyle n}$

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

Estos números muestran un crecimiento más rápido que el exponencial : el número de gráficos de intervalo en vértices no etiquetados es al menos . ^[25] Debido a esta rápida tasa de crecimiento, los gráficos de intervalo no tienen un ancho gemelo acotado . ^[26] ${\displaystyle 3n}$ ${\displaystyle n!/3^{3n}}$

Notas

1. Lekkerkerker y Boland (1962).
2. Fulkerson y Gross (1965); Fishburn (1985)
3. Gilmore y Hoffman (1964).
4. McKee y McMorris (1999); Brandstädt, Le y Spinrad (1999)
5. Hsu (1992).
6. Fishburn (1985); Golumbic (1980)
7. Fishburn (1985).
8. Eckhoff (1993).
9. Roberts (1969); Gardi (2007)
10. Faudree, Flandrin y Ryjáček (1997), pág. 89.
11. Proskurowski y Telle (1999).
12. Beyerl y Jamison (2008).
13. Klavík, Otachi y Šejnoha (2019).
14. Cohen (1978), págs. ix–10.
15. Cohen (1978), págs. 12–33.
16. Bar-Noy y otros (2001).
17. Cormen et al. (2001), pág. 379.
18. Zhang y otros (1994).
19. Golumbic y Shamir (1993).
20. Villanger y otros (2009).
21. Bliznets y otros (2014).
22. Bodlaender (1998).
23. Hanlon (1982), Tabla VIII, pág. 422.
24. Hanlon (1982), Tabla VII, pág. 421.
25. Yang y Pippenger (2017).
26. Bonnet y otros (2022).

Referencias

• Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; Naor, Joseph (Seffi) ; Schieber, Baruch (2001), "Un enfoque unificado para aproximar la asignación y programación de recursos", Journal of the ACM , 48 (5): 1069–1090, CiteSeerX  10.1.1.124.9886 , doi :10.1145/502102.502107, S2CID  12329294
• Beyerl, Jeffery J.; Jamison, Robert E. (2008), "Gráficos de intervalos con restricciones de contención", Actas de la Trigésima Novena Conferencia Internacional del Sureste sobre Combinatoria, Teoría de Grafos y Computación , Congressus Numerantium, vol. 191, págs. 117–128, arXiv : 1109.6675 , MR  2489816
• Bliznets, Ivan; Fomin, Fedor V.; Pilipczuk, Marcin; Pilipczuk, Michał (2014), "Un algoritmo parametrizado subexponencial para la compleción adecuada de intervalos", en Schulz, Andreas S.; Wagner, Dorothea (eds.), Actas del 22.º Simposio Europeo Anual sobre Algoritmos (ESA 2014), Wroclaw, Polonia, 8-10 de septiembre de 2014 , Lecture Notes in Computer Science, vol. 8737, Springer-Verlag, págs. 173-184, arXiv : 1402.3473 , doi :10.1007/978-3-662-44777-2_15, ISBN 978-3-662-44776-5, Número de identificación del sujeto  12385294
• Bodlaender, Hans L. (1998), "Un k -arboreto parcial de grafos con ancho de árbol acotado", Theoretical Computer Science , 209 (1–2): 1–45, doi :10.1016/S0304-3975(97)00228-4, hdl : 1874/18312
• Bonnet, Édouard; Kim, Eun Jung ; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width I: Verificación del modelo FO manejable", Journal of the ACM , 69 (1): A3:1–A3:46, arXiv : 2004.14789 , doi :10.1145/3486655, MR  4402362
• Booth, KS; Lueker, GS (1976), "Prueba de la propiedad de los consecutivos, gráficos de intervalos y planaridad de gráficos utilizando algoritmos de árboles PQ", Journal of Computer and System Sciences , 13 (3): 335–379, doi : 10.1016/S0022-0000(76)80045-1
• Brandstädt, A.; Le, VB; Spinrad, JP (1999), Clases de grafos: un estudio , Monografías SIAM sobre matemáticas discretas y aplicaciones, ISBN 978-0-89871-432-6
• Cohen, Joel E. (1978), Redes alimentarias y nichos espaciales , Monographs in Population Biology, vol. 11, Princeton, NJ: Princeton University Press, págs. 1–189, ISBN 978-0-691-08202-8, PMID683203 ​
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990], Introducción a los algoritmos (2.ª ed.), MIT Press y McGraw-Hill, ISBN 0-262-03293-7
• Corneil, Derek ; Olariu, Stephan; Stewart, Lorna (2009), "La estructura LBFS y el reconocimiento de gráficos de intervalos", SIAM Journal on Discrete Mathematics , 23 (4): 1905–1953, doi :10.1137/S0895480100373455
• Eckhoff, Jürgen (1993), "Gráficos de intervalos extremos", Journal of Graph Theory , 17 (1): 117–127, doi :10.1002/jgt.3190170112
• Faudree, Ralph ; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Gráficos sin garras: un estudio", Discrete Mathematics , 164 (1–3): 87–147, doi : 10.1016/S0012-365X(96)00045-3 , MR  1432221
• Fishburn, Peter C. (1985), Órdenes de intervalos y gráficos de intervalos: un estudio de conjuntos parcialmente ordenados , Wiley-Interscience Series in Discrete Mathematics, Nueva York: John Wiley & Sons
• Fulkerson, DR ; Gross, OA (1965), "Matrices de incidencia y gráficos de intervalo", Pacific Journal of Mathematics , 15 (3): 835–855, doi : 10.2140/pjm.1965.15.835
• Gardi, Frédéric (2007), "La caracterización de Roberts de los gráficos de intervalos propios y unitarios", Discrete Mathematics , 307 (22): 2906–2908, doi :10.1016/j.disc.2006.04.043
• Gilmore, PC; Hoffman, AJ (1964), "Una caracterización de los gráficos de comparabilidad y de los gráficos de intervalo", Revista canadiense de matemáticas , 16 : 539–548, doi : 10.4153/CJM-1964-055-5
• Golumbic, Martin Charles (1980), Teoría de grafos algorítmicos y grafos perfectos , Academic Press, ISBN 978-0-12-289260-8
• Golumbic, Martin Charles ; Shamir, Ron (1993), "Complejidad y algoritmos para razonar sobre el tiempo: un enfoque de teoría de grafos", Journal of the ACM , 40 (5): 1108–1133, CiteSeerX  10.1.1.35.528 , doi :10.1145/174147.169675, S2CID  15708027
• Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), "Lex-BFS y refinamiento de particiones, con aplicaciones a la orientación transitiva, reconocimiento de gráficos de intervalos y pruebas de números consecutivos", Theoretical Computer Science , 234 (1–2): 59–84, doi : 10.1016/S0304-3975(97)00241-7
• Hanlon, Phil (1982), "Conteo de gráficos de intervalos", Transactions of the American Mathematical Society , 272 (2): 383–426, doi : 10.2307/1998705 , JSTOR  1998705, MR  0662044
• Hsu, Wen-Lian (1992), "Una prueba simple para gráficos de intervalos", en Mayr, Ernst W. (ed.), Graph-Theoretic Concepts in Computer Science, 18th International Workshop, WG '92, Wiesbaden-Naurod, Alemania, 19-20 de junio de 1992, Actas , Lecture Notes in Computer Science, vol. 657, Springer, págs. 11-16, doi :10.1007/3-540-56402-0_31, ISBN 978-3-540-56402-7
• Klavík, Pavel; Otachi, Yota; Šejnoha, Jiří (2019), "Sobre las clases de gráficos de intervalos de anidamiento limitado y recuento de longitudes", Algorithmica , 81 (4): 1490–1511, arXiv : 1510.03998 , doi :10.1007/s00453-018-0481-y, MR  3936165, S2CID  254028486
• Lekkerkerker, CG ; Boland, JC (1962), "Representación de un gráfico finito mediante un conjunto de intervalos en la línea real", Fundamenta Mathematicae , 51 : 45–64, doi : 10.4064/fm-51-1-45-64
• McKee, Terry A.; McMorris, FR (1999), Temas de teoría de grafos de intersección , Monografías SIAM sobre matemáticas discretas y aplicaciones, ISBN 978-0-89871-430-2
• Proskurowski, Andrzej; Telle, Jan Arne (1999), "Clases de gráficos con modelos de intervalo restringido", Matemáticas discretas y ciencias de la computación teórica , 3 (4): 167–176, CiteSeerX  10.1.1.39.9532
• Roberts, FS (1969), "Gráficos de indiferencia", en Harary, Frank (ed.), Proof Techniques in Graph Theory , Nueva York, NY : Academic Press , pp. 139-146, ISBN 978-0123242600, OCLC  30287853
• Villanger, Yngve; Heggernes, Pinar ; Pablo, Christophe; Telle, Jan Arne (2009), "La finalización del intervalo es manejable con parámetros fijos", SIAM Journal on Computing , 38 (5): 2007–2020, CiteSeerX  10.1.1.73.8999 , doi :10.1137/070710913, S2CID  8521105
• Yang, Joyce C.; Pippenger, Nicholas (2017), "Sobre la enumeración de gráficos de intervalos", Actas de la American Mathematical Society , Serie B, 4 : 1–3, arXiv : 1609.02479 , doi :10.1090/bproc/27, MR  3613306, S2CID  38225412
• Zhang, Peisen; Schon, Eric A.; Fischer, Stuart G.; Cayanis, Eftihia; Weiss, Janie; Kistler, Susan; Bourne, Philip E. (1994), "Un algoritmo basado en la teoría de grafos para el ensamblaje de contigs en el mapeo físico del ADN", Bioinformatics , 10 (3): 309–317, doi :10.1093/bioinformatics/10.3.309, PMID  7922688

Enlaces externos

• "Gráfico de intervalos", Sistema de información sobre clases de grafos y sus inclusiones
• Weisstein, Eric W. , "Gráfico de intervalo", MathWorld