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.

Sia {I₁, I₂, ..., I_n} ⊂ P(R) un insieme di intervalli.

Il grafo d'intervallo corrispondente è G = (V, E), dove

• V = {I₁, I₂, ..., I_n}, 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 M₁, M₂, ..., M_k tale che per un qualsiasi v ∈ M_i ∩ M_k, dove i < k, avviene anche che v ∈ M_j per qualsiasi M_j, i ≤ j ≤ k.^[1]

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]

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]

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]

• 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.

• (EN) interval graph, su Information System on Graph Classes and their Inclusions.
• (EN) Eric W. Weisstein, Grafo d'intervallo, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica