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.
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
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]
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]
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.
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 .
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 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]
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]
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]
enumeración combinatoria
El número de gráficos de intervalo conectados en vértices sin etiquetar, para , es: [23]
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]
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]
Notas
^ ab Lekkerkerker y Boland (1962).
^ Fulkerson y bruto (1965); Quema de pescado (1985)
^ ab Gilmore y Hoffman (1964).
^ McKee y McMorris (1999); Brandstädt, Le y Spinrad (1999)
^ Hsu (1992).
^ Quemadura de pescado (1985); Golúmbico (1980)
^ Quemadura de pescado (1985).
^ Eckhoff (1993).
^ Roberts (1969); Gardi (2007)
^ Faudree, Flandrin y Ryjáček (1997), pág. 89.
^ Proskurowski y Telle (1999).
^ Beyerl y Jamison (2008).
^ Klavík, Otachi y Šejnoha (2019).
^ Cohen (1978), págs. ix-10.
^ Cohen (1978), págs. 12-33.
^ Bar-Noy y col. (2001).
^ Cormen et al. (2001), pág. 379.
^ Zhang y otros. (1994).
^ Golumbic y Shamir (1993).
^ Villanger y col. (2009).
^ Bliznets y otros. (2014).
^ Bodlaender (1998).
^ Hanlon (1982), Tabla VIII, p. 422.
^ Hanlon (1982), Tabla VII, pág. 421.
^ Yang y Pippenger (2017).
^ 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 completar intervalos adecuados", 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
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
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
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
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 en 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
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