Loading AI tools
Da Wikipedia, l'enciclopedia libera
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 {I1, I2, ..., In} ⊂ P(R) un insieme di intervalli.
Il grafo d'intervallo corrispondente è G = (V, E), dove
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]
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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.