Intervallgraph

Die Intervallgraphen bilden in der Graphentheorie eine spezielle Klasse von Graphen.

Die erste Erwähnung findet man bei György Hajós 1957.^[1] Einen wesentlichen Schub bekam das Interesse an Intervallgraphen durch einen Vorstoß von Seymour Benzer 1959, der eine These zur Struktur von Genen überprüfen wollte.^[2] Zu den zeitgenössischen Anwendungen gehören unter anderem Probleme des Scheduling, archäologische Seriation,^[3] Verhaltenspsychologie,^[4] Temporallogik,^[5][6] Schaltungsdesign und das Human Genome Project.^[7]

Ein Intervallgraph und ein Intervallmodell.

Definition

Sei ${\displaystyle G=(V,E)}$ ein Graph. Ist ${\displaystyle {\mathcal {I}}:=\{I_{x}\}_{x\in V}}$ eine Familie von Intervallen dergestalt, dass gilt

${\displaystyle {\begin{aligned}I_{x}\cap I_{y}\neq \emptyset \Leftrightarrow (x,y)\in E,\end{aligned}}}$

so heißt ${\displaystyle {\mathcal {I}}}$ Intervallmodell für ${\displaystyle G}$. Graphen, die ein Intervallmodell besitzen, heißen Intervallgraphen.

Zwei Beispiele

Raumplanung

Eine Menge von ${\displaystyle n\in \mathbb {N} }$ Vorlesungen ${\displaystyle V:=\{v_{1},v_{2}\dots v_{n}\}}$ finden jeweils in einem Zeitintervall ${\displaystyle T_{i},i\in \{1,2\dots n\}}$ statt. Wie viele Räume genügen, wenn jede Vorlesung stets einen eigenen Raum beansprucht, während sie stattfindet?

Betrachte den Intervallgraphen ${\displaystyle G:=(V,E)}$, wobei für ${\displaystyle i\neq j}$ gelte, dass ${\displaystyle (v_{i},v_{j})\in E:\Leftrightarrow T_{i}\cap T_{j}\neq \emptyset }$. Falls den Knoten jeweils ein Raum so zugeordnet werden kann, dass keine benachbarten Knoten denselben Raum beanspruchen, genügt diese Konstruktion der geforderten Bedingung, dass gleichzeitige Vorlesungen verschiedene Räume bekommen. Solch eine Belegung der Knoten ist eine Färbung.

In allgemeinen Graphen ist die Bestimmung einer minimalen Färbung ein NP-schweres Problem. In perfekten Graphen, zu denen die Intervallgraphen gehören, lässt es sich in Linearzeit lösen.^[8]

Kühlproblem

Nimm an, für eine Menge von ${\displaystyle n\in \mathbb {N} }$ Stoffen ${\displaystyle S:=\{s_{1},s_{2}\dots s_{n}\}}$ wäre bekannt, dass man sie bei einer Temperatur zwischen ${\displaystyle t_{i}}$ und ${\displaystyle t_{i}'}$ Grad lagern müsste (${\displaystyle i\in \{1,2\dots n\}}$). Wie viele Kühlschränke reichen aus, um alle zu lagern?

Ordne jedem Stoff das Intervall ${\displaystyle T_{i}:=[t_{i},t_{i}']}$ zu und bezeichne mit ${\displaystyle G}$ den Intervallgraph über den Knoten ${\displaystyle s_{i}}$ und einer Kante zwischen zwei Stoffen genau dann, wenn die zugehörigen Intervalle einen nicht verschwindenden Schnitt besitzen.

Ist nun ${\displaystyle C\subseteq S}$ eine Clique von ${\displaystyle G}$, werden die Intervalle ${\displaystyle \{T_{c}\}_{c\in C}}$ aufgrund der Helly-Eigenschaft von Intervallen einen gemeinsamen Schnittpunkt ${\displaystyle \tau _{C}}$ besitzen. Ein Kühlschrank, der auf diese Temperatur ${\displaystyle \tau _{C}}$ eingestellt wird, wäre dann geeignet, um alle Stoffe der Clique zu lagern. So reduziert sich die Eingangsfrage nach den Kühlschränken auf die Bestimmung einer minimalen Cliquenüberdeckung im Intervallgraph ${\displaystyle G}$.

In allgemeinen Graphen ist die Bestimmung einer minimalen Clickenüberdeckung ein NP-schweres Problem. In Kreisbogengraphen, zu denen die Intervallgraphen gehören, lässt es sich in Linearzeit lösen.^[9]

Weitere Charakterisierungen

Sei nun stets G ein ungerichteter Graph. Die Äquivalenz folgender Aussagen, ist Gegenstand des Satzes von Gilmore und Hoffman^[10]:

• G ist ein Intervallgraph.
• G ist chordal und sein Komplementgraph ist transitiv orientierbar.
• Die maximalen Cliquen von G können so geordnet werden, dass für jeden Knoten die maximalen Cliquen, die ihn enthalten, in der Ordnung konsekutiv auftreten.

Ausgehend von der letzten Charakterisierung gaben Booth und Lueker einen Erkennungsalgorithmus mit linearer Laufzeit an, wofür sie die Datenstruktur der PQ-Bäume einführten.^[11] Fulkerson and Gross formulierten diese Charakterisierung als eine Eigenschaft von sogenannten Cliquenmatrizen.^[12]

Lekkerkerker und Boland konnten zeigen, dass auch Folgendes eine äquivalente Charakterisierung von Intervallgraphen ist:^[13]

1. G ist chordal und
2. je drei Knoten von G können so geordnet werden, dass jeder Pfad vom ersten zum dritten Knoten über einen Nachbarn des zweiten verläuft.

Ein Knotentripel, das die Bedingung aus (2) nicht erfüllt, heißt astroidales Tripel. In einem solchen Tripel sind also je zwei Knoten durch einen Pfad verbunden, der die Nachbarknoten des dritten meidet. Ausgehend von dieser Charakterisierung zeigten sie auch:

• G ist genau dann ein Intervallgraph, wenn er für alle ${\displaystyle n\in \mathbb {N} }$ keinen der unten abgebildeten Graphen ${\displaystyle {\text{I}}}$,${\displaystyle {\text{II}}}$, ${\displaystyle {\text{III}}_{n}}$, ${\displaystyle {\text{IV}}_{n}}$ oder ${\displaystyle {\text{V}}_{n}}$ als induzierten Teilgraphen enthält.

Die Graphen mit gestrichelten Kanten bilden unendliche Familien, wobei für die gestrichelte Kante für jedes ${\displaystyle n\in \mathbb {N} }$ ein ${\displaystyle P_{n}}$ eingesetzt werden kann. Für die Familien ${\displaystyle {\text{III}}_{n}}$ und ${\displaystyle {\text{IV}}_{n}}$ seien die Konten dieses Pfades adjazent zu den weißen und weiter oben eingezeichneten Knoten. Schwarz markiert sind stets die astroidalen Tripel.

• Vollständige Liste der in Intervallgraphen verbotenen induzierten Untergraphen
• 
  ${\displaystyle {\text{I}}}$
• 
  ${\displaystyle {\text{II}}}$
• 
  ${\displaystyle {\text{III}}_{n}}$
• 
  ${\displaystyle {\text{IV}}_{n}}$
• 
  ${\displaystyle {\text{V}}_{n}}$

Literatur

• Alan Gibbons: Algorithmic Graph Theory. Cambridge University Press, Cambridge, Cambridgeshire / New York 1985, ISBN 978-0-521-28881-1 (englisch).

Weblinks

• Intervallgraphen im Information System on Graph Classes and their Inclusions.