Grafo d'intervallo

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca
Sette intervalli sulla linea reale e il corrispondente grafo d'intervallo a sette vertici.

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]

  1. ^ a b c d Fishburn (1985)
  2. ^ a b Golumbic (1980).
  3. ^ Gilmore & Hoffman (1964)
  4. ^ Faudree, Flandrin & Ryjáček (1997), p. 89.
  5. ^ Roberts (1969)
  6. ^ Bodlaender (1998).
  7. ^ Eckhoff (1993).
  8. ^ Cohen1978, Cohen (1978)
  9. ^ Cohen1978, Cohen (1978)
  10. ^ Zhang, Zhang, Schon, Fischer & Cayanis (1994).
  11. ^ Bar-Noy, Bar-Noy, Bar-Yehuda, Freund & Naor (2001.
  12. ^ Golumbic & Shamir (1993).

Bibliografia[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica
Estratto da "https://it.wikipedia.org/w/index.php?title=Grafo_d%27intervallo&oldid=131915762"