Indice
Grafo d'intervallo
Nella teoria dei grafi, un grafo d'intervallo è il grafo d'intersezione di un multiinsieme di intervalli sulla linea reale. Ha un solo vertice per ciascun intervallo dell'insieme, e uno spigolo tra ogni coppia di vertici corrispondenti agli intervalli che intersecano.
Definizione
[modifica | modifica wikitesto]Sia {I1, I2, ..., In} ⊂ P(R) un insieme di intervalli.
Il grafo d'intervallo corrispondente è G = (V, E), dove
- V = {I1, I2, ..., In}, e
- {Iα, Iβ} ∈ E se e solo se Iα ∩ Iβ ≠ ∅.
Da questa costruzione si può verificare una proprietà comune posseduta da tutti i grafi d'intervallo. Ossia, il grafo G è un grafo d'intervallo se e solo se le cricche massimali di G si possono porre nell'ordine M1, M2, ..., Mk tale che per un qualsiasi v ∈ Mi ∩ Mk, dove i < k, avviene anche che v ∈ Mj per qualsiasi Mj, i ≤ j ≤ k.[1]
Algoritmi efficienti di riconoscimento
[modifica | modifica wikitesto]Determinare se un dato grafo G = (V, E) è un grafo d'intervallo può essere fatto nel tempo O(|V|+|E|) cercando un ordinamento delle cricche di G che sia consecutivo rispetto all'inclusione dei vertici.
L'algoritmo originale di riconoscimento in tempo lineare di Booth & Lueker (1976) si basa sulla loro complessa struttura dati dell'albero PQ, ma Habib, McConnell, Paul & Viennot (2000) mostrarono come risolvere il problema più semplicemente usando la ricerca lessicografica in ampiezza, basata sul fatto che un grafo è un grafo d'intervallo se e solo se è cordale e il suo complemento è un grafo di comparabilità.[1][2]
Famiglie di grafi correlate
[modifica | modifica wikitesto]I grafi d'intervallo sono grafi cordali e quindi grafi perfetti.[1][2] I loro complementi appartengono alla classe dei grafi di comparabilità,[3] e le relazioni di comparabilità sono precisamente gli ordini d'intervallo.[1]
I grafi d'intervallo che hanno una rappresentazione degli intervalli in cui ogni due intervalli sono o disgiunti o nidificati sono grafi banalmente perfetti.
I grafi d'intervallo propri sono grafi d'intervallo che hanno una rappresentazione degli intervalli in cui nessun intervallo contiene propriamente nessun altro intervallo; i grafi d'intervallo unitari sono i grafi d'intervallo che hanno una rappresentazione degli intervalli in cui ciascun intervallo ha lunghezza unitaria. Ogni grafo d'intervallo proprio è un grafo senza stella. Tuttavia, l'inverso non è vero. Ogni grafo senza stella non è necessariamente un grafo d'intervallo proprio.[4] Se la collezione di segmenti in questione è un insieme, cioè non è consentita alcuna ripetizione di segmenti, allora il grafo è un grafo d'intervallo unitario se e solo se è un grafo d'intervallo proprio.[5]
I grafi d'intersezione degli archi di un cerchio formano grafi con archi circolari, una classe di grafi che contiene i grafi d'intervallo. I grafi trapezoidi, intersezioni di trapezoidi i cui lati paralleli giacciono tutti sulle stesse due linee parallele, sono anch'essi una generalizzazione dei grafi d'intervallo.
L'ampiezza dei cammini di un grafo d'intervallo è la dimensione della sua cricca massima meno uno (o equivalentemente, il suo numero cromatico meno uno), e l'ampiezza dei cammini di un qualsiasi grafo G è uguale alla più piccola ampiezza dei cammini di un grafo d'intervallo che contiene G come sottografo.[6]
I grafi d'intervallo connessi senza triangoli sono esattamente gli alberi millepiedi o alberi "caterpillar".[7]
Applicazioni
[modifica | modifica wikitesto]La teoria matematica dei grafi d'intervallo fu sviluppata con uno sguardo alle applicazioni da ricercatori presso il dipartimento di matematica della RAND Corporation, che includeva giovani ricercatori come Peter C. Fishburn e studenti come Alan C. Tucker e Joel E. Cohen, oltre a capiscuola come Delbert Fulkerson e (spesso in visita) Victor Klee.[8] Cohen applicò i grafi d'intervallo a modelli matematici di biologia delle popolazioni, specificamente alle reti alimentari.[9]
Altre applicazioni comprendono la genetica, la bioinformatica e l'informatica. Trovare un insieme di intervalli che rappresentano un grafo d'intervallo può essere usato anche come modo di assemblare sottosequenze contigue nella mappatura del DNA.[10] I grafi d'intervallo si usano per rappresentare i problemi di allocazione delle risorse nella ricerca operativa e nella teoria della schedulazione. Ciascun intervallo rappresenta la richiesta di una risorsa per uno specifico periodo di tempo; il problema dell'insieme indipendente con il massimo peso per il grafo rappresenta il problema di trovare il miglior sottoinsieme di richieste che possono essere soddisfatte senza conflitti.[11] I grafi d'intervallo giocano anche un importante ruolo nel ragionamento temporale.[12]
Note
[modifica | modifica wikitesto]- ^ a b c d Fishburn (1985)
- ^ a b Golumbic (1980).
- ^ Gilmore & Hoffman (1964)
- ^ Faudree, Flandrin & Ryjáček (1997), p. 89.
- ^ Roberts (1969)
- ^ Bodlaender (1998).
- ^ Eckhoff (1993).
- ^ Cohen1978, Cohen (1978)
- ^ Cohen1978, Cohen (1978)
- ^ Zhang, Zhang, Schon, Fischer & Cayanis (1994).
- ^ Bar-Noy, Bar-Noy, Bar-Yehuda, Freund & Naor (2001.
- ^ Golumbic & Shamir (1993).
Bibliografia
[modifica | modifica wikitesto]- Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph (Seffi) Naor e Baruch Schieber, A unified approach to approximating resource allocation and scheduling, in Journal of the ACM, vol. 48, n. 5, 2001, pp. 1069–1090, DOI:10.1145/502102.502107.
- Hans L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, in Theoretical Computer Science, vol. 209, 1–2, 1998, pp. 1–45, DOI:10.1016/S0304-3975(97)00228-4.
- K. S. Booth e G. S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, in J. Comput. System Sci., vol. 13, n. 3, 1976, pp. 335–379, DOI:10.1016/S0022-0000(76)80045-1.
- Joel E. Cohen, Food webs and niche space, Monographs in Population Biology, vol. 11, Princeton, NJ, Princeton University Press, 1978, pp. xv+1–190, ISBN 978-0-691-08202-8.
- Jürgen Eckhoff, Extremal interval graphs, in Journal of Graph Theory, vol. 17, n. 1, 1993, pp. 117–127, DOI:10.1002/jgt.3190170112.
- Ralph Faudree, Evelyne Flandrin e Zdeněk Ryjáček, Claw-free graphs — A survey, in Discrete Mathematics, vol. 164, 1–3, 1997, pp. 87–147, DOI:10.1016/S0012-365X(96)00045-3, MR 1432221.
- Peter C. Fishburn, Interval orders and interval graphs: A study of partially ordered sets, Wiley-Interscience Series in Discrete Mathematics, New York, John Wiley & Sons, 1985.
- D. R. Fulkerson e O. A. Gross, Incidence matrices and interval graphs, in Pacific Journal of Mathematics, vol. 15, 1965, pp. 835–855.
- P. C. Gilmore e A. J. Hoffman, A characterization of comparability graphs and of interval graphs, in Can. J. Math., vol. 16, 1964, pp. 539–548, DOI:10.4153/CJM-1964-055-5.
- Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980, ISBN 0-12-289260-7.
- Martin Charles Golumbic e Ron Shamir, Complexity and algorithms for reasoning about time: a graph-theoretic approach, in J. Assoc. Comput. Mach., vol. 40, 1993, pp. 1108–1133.
- Michel Habib, Ross McConnell, Christophe Paul e Laurent Viennot, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing (ps), in Theor. Comput. Sci., vol. 234, 2000, pp. 59–84, DOI:10.1016/S0304-3975(97)00241-7.
- F.S. Roberts, Indifference graphs, in Proof Techniques in Graph Theory, Academic Press, New York, 1969, pp. 139–146.
- Peisen Zhang, Eric A. Schon, Stuart G. Fischer, Eftihia Cayanis, Janie Weiss, Susan Kistler e Philip E. Bourne, An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA, in Bioinformatics, vol. 10, n. 3, 1994, pp. 309–317, DOI:10.1093/bioinformatics/10.3.309.
Collegamenti esterni
[modifica | modifica wikitesto]- (EN) interval graph, su Information System on Graph Classes and their Inclusions.
- (EN) Eric W. Weisstein, Grafo d'intervallo, su MathWorld, Wolfram Research.