Intervalgraaf

Een intervalgraaf is een voorstelling in graafvorm van een verzameling van intervallen op de getallenlijn. Elke knoop in de graaf stelt een interval uit de verzameling voor, en twee knopen zijn verbonden door een kant indien de corresponderende intervallen elkaar geheel of gedeeltelijk overlappen.

De intervalgraaf overeenkomend met de zeven intervallen A tot G op de reële lijn.

Formele definitie

Stel :$I_{1},I_{2},\ldots ,I_{n}\subset \mathbb {R}$ zijn n intervallen. Dan is de overeenkomstige intervalgraaf $G=(V,E)~$, met knopenverzameling V en kantenverzameling E, waarbij

$V=\{I_{1},I_{2},\ldots ,I_{n}\}$

en een kant

$\{I_{\alpha },I_{\beta }\}\in E\iff I_{\alpha }\cap I_{\beta }\neq \emptyset .$

De verzameling $\{I_{1},I_{2},\ldots ,I_{n}\}$ noemt men de intervalvoorstelling van graaf $G$.

Eigenschappen

Intervalgrafen zijn chordale grafen en bijgevolg ook perfecte grafen.

Als men aan de intervallen een partiële orde oplegt gedefinieerd door de relatie: "I_i ≤ I_j als interval I_i volledig links ligt van interval I_j op de getallenlijn", dan is de hiermee corresponderende graaf de complementgraaf van de intervalgraaf.

Elke geïnduceerde deelgraaf van een intervalgraaf is ook een intervalgraaf. Een geïnduceerde deelgraaf bestaat uit een deelverzameling van de knopen en enkel die kanten van de graaf die knopen uit die deelverzameling verbinden.

Het beslissingsprobleem: is een gegeven graaf G = (V, E) een intervalgraaf? kan opgelost worden in lineaire tijd O(n).

Verwante grafen

De "klauw" is de volledige bipartiete graaf K_1,3.

• Een eenheidsintervalgraaf (Engels: unit interval graph) is een intervalgraaf waarin elk interval van eenheidslengte is.

• Een echte intervalgraaf (Engels: proper interval graph) is een intervalgraaf waarin geen enkel interval een ander interval omsluit, dit wil zeggen : geen enkel interval is een echte deelverzameling van een ander interval.

Elke echte intervalgraaf is een "klauwvrije graaf" (Engels: claw-free graph); dit betekent dat de graaf geen "klauw" als geïnduceerde deelgraaf heeft. "Klauw" is een andere naam voor de volledige bipartiete graaf K_1,3, dit is een stervormige graaf met een centrale knoop die verbonden is met drie andere knopen. Een echte intervalgraaf bezit nergens vier knopen die op deze manier met elkaar verbonden zijn. Het omgekeerde is echter niet waar: niet elke klauwvrije graaf is een echte intervalgraaf.

De klassen van echte intervalgrafen en eenheidsintervalgrafen vallen samen. Elke eenheidsintervalgraaf is een echte intervalgraaf, immers geen enkel interval is volledig omsloten door een ander interval van gelijke lengte. Omgekeerd is elke echte intervalgraaf een eenheidsintervalgraaf, omdat we de eindpunten van de intervallen kunnen aanpassen totdat alle intervallen eenheidslengte hebben, zonder de graaf zelf te veranderen. De beweringen "G is een eenheidsintervalgraaf" en "G is een echte intervalgraaf" zijn dus gelijkwaardig.

Een cirkelbooggraaf met de corresponderende bogen op een cirkel

• Cirkelbooggrafen (Engels: circular-arc graphs) stellen de overlappingen voor van bogen op een cirkel. Ze vormen een veralgemening van intervalgrafen. Indien er een punt op de cirkelomtrek is dat niet tot een boog behoort, kan de cirkel in dat punt doorgeknipt worden en uitgerold tot een rechte, wat resulteert in een intervalgraaf (dat is bijvoorbeeld in de figuur hiernaast niet mogelijk). Hoewel cirkelbooggrafen veel lijken op intervalgrafen, zijn er belangrijke verschillen: cirkelbooggrafen zijn niet altijd perfecte grafen.

Toepassingen

Intervalgrafen worden onder meer gebruikt in de computerwetenschap, bio-informatica, operationeel onderzoek en genetica.

Externe links

• Weisstein, Eric W. "Interval Graph." From MathWorld--A Wolfram Web Resource
• GraphClasses.org: Interval graph

Bronnen, noten en/of referenties