Gráfico de intervalos

Gráfico de intersección de intervalos en la recta numérica real

Siete intervalos en la recta real y el correspondiente gráfico de intervalos de siete vértices.

En teoría de grafos , un gráfico de intervalos es un gráfico no dirigido formado a partir de un conjunto de intervalos sobre 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

Un gráfico de intervalos 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 vi para cada intervalo Si 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 forman un triple asteroidal (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 cordal y libre de AT. ^[1]

Otras caracterizaciones:

• Un gráfico es un gráfico de intervalo si y sólo si sus camarillas máximas se pueden ordenar de manera que cada vértice que pertenece a dos de estas camarillas también pertenezca a todas las camarillas entre ellos en el orden. Es decir, para cada vez con , también ocurre que cuando sea . ^[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 subgrafo inducido y es el complemento de un gráfico de comparabilidad . ^[3] ${\displaystyle C_{4}}$

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

Algoritmo de reconocimiento eficiente

Se puede determinar si un gráfico dado es un gráfico de intervalo en el tiempo buscando un orden de las camarillas máximas que sea consecutivo 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. ^[5] ${\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) mostraron cómo resolver el problema de manera más simple usando la 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 . ^[6] En Corneil, Olariu & Stewart (2009) se describe un enfoque similar que utiliza un algoritmo LexBFS de 6 barridos.

Familias relacionadas de gráficos

Por la caracterización de los gráficos de intervalo como gráficos cordales sin AT, ^[1] 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 , ^[3] y las relaciones de comparabilidad son precisamente los órdenes de intervalo . ^[7]

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 a la vez una gráfica dividida y una permutación. grafico .

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 sólo 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 tales que la intersección de los conjuntos de aristas de los gráficos de intervalo es . ${\displaystyle G}$ ${\displaystyle G}$

Las gráficas de intersección de arcos de 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 todos en las mismas dos líneas paralelas, también son una generalización de las gráficas de intervalo.

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

Gráficos de intervalo 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. ^[9] 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. ^[10]

Un gráfico 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 amplía la idea de gráficos de intervalos propios de modo que un gráfico de intervalos propios 0 es un gráfico de intervalos propios. ^[11] Un gráfico de intervalo se llama impropio 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 0-impropio es un gráfico de intervalos adecuados. ^[12] Un gráfico de intervalo está anidado si no hay una cadena de longitud de intervalos anidados entre sí. Esta es una generalización de los gráficos de intervalos adecuados, ya que los gráficos de intervalos 1 anidados son exactamente gráficos de intervalos adecuados. ^[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 miras a aplicaciones por parte de investigadores del departamento de matemáticas de la Corporación RAND , 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 . ^[14] Cohen aplicó gráficos de intervalos a modelos matemáticos de biología de poblaciones , específicamente a 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 de peso máximo para el gráfico representa el problema de encontrar el mejor subconjunto de solicitudes que puedan satisfacerse sin conflictos. ^[16] 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. ^[17]

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

Finalizaciones de intervalos y ancho de ruta

Si es un gráfico arbitrario, una finalización de intervalo es un gráfico de intervalo en el mismo conjunto de vértices que contiene un subgrafo. La versión parametrizada de la finalización del intervalo (encontrar un supergrafo de intervalo con k aristas adicionales) es manejable con parámetros fijos y, además, se puede resolver en un 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 camarilla máxima (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 subgrafo. . ^[22] ${\displaystyle G}$ ${\displaystyle G}$

enumeración combinatoria

El número de gráficos de intervalo conectados en vértices sin etiquetar, 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 el OEIS )

Sin el supuesto de conectividad, las cifras son mayores. El número de gráficos de intervalo en vértices sin etiquetar, no necesariamente conectados, es: ^[24] ${\displaystyle n}$

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

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

Notas

1. Lekkerkerker y Boland (1962).
2. Fulkerson y bruto (1965); Quema de pescado (1985)
3. Gilmore y Hoffman (1964).
4. McKee y McMorris (1999); Brandstädt, Le y Spinrad (1999)
5. Hsu (1992).
6. Quemadura de pescado (1985); Golúmbico (1980)
7. Quemadura de pescado (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 col. (2001).
17. Cormen et al. (2001), pág. 379.
18. Zhang y otros. (1994).
19. Golumbic y Shamir (1993).
20. Villanger y col. (2009).
21. Bliznets y otros. (2014).
22. Bodlaender (1998).
23. Hanlon (1982), Tabla VIII, p. 422.
24. Hanlon (1982), Tabla VII, pág. 421.
25. Yang y Pippenger (2017).
26. Capo y col. (2022).

Referencias

• Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; Naor, José (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 intervalo con restricciones de contención", Actas de la trigésima novena conferencia internacional del sudeste sobre combinatoria, teoría de grafos y computación , Congressus Numerantium, vol. 191, págs. 117-128, arXiv : 1109.6675 , SEÑOR  2489816
• Bliznets, Iván; Fomin, Fedor V.; Pilipczuk, Marcin; Pilipczuk, Michał (2014), "Un algoritmo parametrizado subexponencial para la finalización adecuada de intervalos", en Schulz, Andreas S.; Wagner, Dorothea (eds.), Actas del 22º Simposio europeo anual sobre algoritmos (ESA 2014), Wroclaw, Polonia, 8 al 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, S2CID  12385294
• Bodlaender, Hans L. (1998), "Un k -arboretum parcial de gráficos con ancho de árbol acotado", Ciencias de la Computación Teórica , 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: Comprobación del modelo FO manejable", Journal of the ACM , 69 (1): A3:1–A3:46, arXiv : 2004.14789 , doi :10.1145/3486655, MR  4402362
• Stand, KS; Lueker, GS (1976), "Prueba de la propiedad de los consecutivos, gráficos de intervalo y planaridad de gráficos utilizando algoritmos de árbol 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 gráficos: una encuesta , Monografías de SIAM sobre aplicaciones y matemáticas discretas, ISBN 978-0-89871-432-6
• Cohen, Joel E. (1978), Redes alimentarias y nichos de espacio , Monografías de biología de poblaciones, vol. 11, Princeton, Nueva Jersey: Princeton University Press, págs. 1–189, ISBN 978-0-691-08202-8, PMID  683203
• 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 intervalo", Revista SIAM de Matemáticas Discretas , 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: una encuesta", Matemáticas discretas , 164 (1–3): 87–147, doi : 10.1016/S0012-365X(96)00045-3 , SEÑOR  1432221
• Fishburn, Peter C. (1985), Órdenes de intervalos y gráficos de intervalos: un estudio de conjuntos parcialmente ordenados , Serie Wiley-Interscience en Matemáticas Discretas, Nueva York: John Wiley & Sons
• Fulkerson, DR ; Gross, OA (1965), "Matrices de incidencia y gráficos de intervalos", 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 gráficos de intervalos unitarios y propios", Matemáticas discretas , 307 (22): 2906–2908, doi :10.1016/j.disc.2006.04.043
• Gilmore, ordenador personal; Hoffman, AJ (1964), "Una caracterización de gráficos de comparabilidad y de gráficos de intervalo", Canadian Journal of Mathematics , 16 : 539–548, doi : 10.4153/CJM-1964-055-5
• Golumbic, Martin Charles (1980), Teoría algorítmica de grafos y gráficos perfectos , Academic Press, ISBN 978-0-12-289260-8
• Golumbic, Martín Carlos ; Shamir, Ron (1993), "Complejidad y algoritmos para razonar sobre el tiempo: un enfoque teórico 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; Pablo, Christophe; Viennot, Laurent (2000), "Lex-BFS y refinamiento de particiones, con aplicaciones a orientación transitiva, reconocimiento de gráficos de intervalos y pruebas consecutivas", Ciencias de la Computación Teórica , 234 (1–2): 59–84, doi : 10.1016/ S0304-3975(97)00241-7
• Hanlon, Phil (1982), "Gráficos de intervalos de conteo", Transactions of the American Mathematical Society , 272 (2): 383–426, doi : 10.2307/1998705 , JSTOR  1998705, MR  0662044
• Hsu, Wen-Lian (1992), "A simple test for intervalo graphs", en Mayr, Ernst W. (ed.), Graph-Theoretic Concepts in Computer Science, 18º Taller Internacional, WG '92, Wiesbaden-Naurod, Alemania , 19 y 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
• Klavík, Pavel; Otachi, Yota; Šejnoha, Jiří (2019), "Sobre las clases de gráficos de intervalo de anidamiento limitado y recuento de longitudes", Algorithmica , 81 (4): 1490–1511, arXiv : 1510.03998 , doi :10.1007/s00453-018-0481-y, SEÑOR  3936165, S2CID  254028486
• Lekkerkerker, CG ; Boland, JC (1962), "Representación de un gráfico finito mediante un conjunto de intervalos sobre la recta 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 de SIAM sobre aplicaciones y matemáticas discretas, ISBN 978-0-89871-430-2
• Proskurowski, Andrzej; Telle, Jan Arne (1999), "Clases de gráficos con modelos de intervalo restringido", Matemáticas discretas e informática teórica , 3 (4): 167–176, CiteSeerX  10.1.1.39.9532
• Roberts, FS (1969), "Gráficos de indiferencia", en Harary, Frank (ed.), Técnicas de prueba en teoría de grafos , Nueva York, NY : Academic Press , págs. 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 intervalo", Actas de la Sociedad Matemática Estadounidense , Serie B, 4 : 1–3, arXiv : 1609.02479 , doi : 10.1090/bproc/27, MR  3613306, S2CID  38225412
• Zhang, Peisen; Schön, 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 Gráficos y sus Inclusiones
• Weisstein, Eric W. , "Gráfico de intervalos", MathWorld