Wikipedia

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.

Sette intervalli sulla linea reale e il corrispondente grafo d'intervallo a sette vertici.

Definizione modifica

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

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

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

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

  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

Collegamenti esterni modifica

  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"