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] Schaltkreisdesign und das Human Genome Project.[6]

Ein Intervallgraph und ein Intervallmodell.

DefinitionBearbeiten

Sei   ein Graph. Ist   eine Familie von Intervallen dergestalt, dass gilt

 

so heißt   Intervallmodell für  . Graphen, die ein Intervallmodell besitzen, heißen Intervallgraphen.

Zwei BeispieleBearbeiten

RaumplanungBearbeiten

Eine Menge von   Vorlesungen   finden jeweils in einem Zeitintervall   statt. Wie viele Räume genügen, wenn jede Vorlesung stets einen eigenen Raum beansprucht, während sie stattfindet?

Betrachte den Intervallgraphen  , wobei für   gelte, dass  . 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.[7]

KühlproblemBearbeiten

Nimm an, für eine Menge von   Stoffen   wäre bekannt, dass man sie bei einer Temperatur zwischen   und   Grad lagern müsste ( ). Wie viele Kühlschränke reichen aus, um alle zu lagern?

Ordne jedem Stoff das Intervall   zu und bezeichne mit   den Intervallgraph über den Knoten   und einer Kante zwischen zwei Stoffen genau dann, wenn die zugehörigen Intervalle einen nicht verschwindenden Schnitt besitzen.

Ist nun   eine Clique von  , werden die Intervalle   aufgrund der Helly-Eigenschaft von Intervallen einen gemeinsamen Schnittpunkt   besitzen. Ein Kühlschrank, der auf diese Temperatur   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  .

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.[8]

Weitere CharakterisierungenBearbeiten

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

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.[10] Fulkerson and Gross formulierten diese Charakterisierung als eine Eigenschaft von sogenannten Cliquenmatrizen.[11]

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

  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   keinen der unten abgebildeten Graphen  , ,  ,   oder   als induzierten Teilgraphen enthält.

Die Graphen mit gestrichelten Kanten bilden unendliche Familien, wobei für die gestrichelte Kante für jedes   ein   eingesetzt werden kann. Für die Familien   und   seien die Konten dieses Pfades adjazent zu den weißen und weiter oben eingezeichneten Knoten. Schwarz markiert sind stets die astroidalen Tripel.

LiteraturBearbeiten

  • Alan Gibbons: Algorithmic Graph Theory. Cambridge University Press, Cambridge Cambridgeshire; New York 27. Juni 1985, ISBN 978-0-521-28881-1.

WeblinksBearbeiten

EinzelnachweiseBearbeiten

  1. G. Hajös: Über eine Art von Graphen. In: Intern. Math. Nachr.. 11, Nr. 65, 1957.
  2. Seymour Benzer: On the topology of the genetic fine structure. In: Proceedings of the National Academy of Sciences. 45, Nr. 11, 1959, S. 1607. PMC 222769 (freier Volltext).
  3. David Kendall: Incidence matrices, interval graphs and seriation in archeology. In: Pacific Journal of mathematics. 28, Nr. 3, 1969, S. 565–570.
  4. Clyde H. Coombs, J. E. Smith: On the detection of structure in attitudes and developmental processes.. In: Psychological Review. 80, Nr. 5, 1973, S. 337.
  5. Jürgen Dorn: Temporal reasoning in sequence graphs. In: AAAI . Citeseer, S. 735–740.
  6. Richard M. Karp: Mapping the genome: some combinatorial problems arising in molecular biology. In: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing . ACM, S. 278–285.
  7. Martin Charles Golumbic: Algorithmic graph theory and perfect graphs 1980.
  8. Wen-Lian Hsu, Kuo-Hui Tsai: Linear time algorithms on circular-arc graphs. In: Information Processing Letters. 40, Nr. 3, 8. November 1991, ISSN 0020-0190, S. 123–129. doi:10.1016/0020-0190(91)90165-E.
  9. P. C. Gilmore, A. J. Hoffman: A characterization of comparability graphs and of interval graphs. In: Canadian Journal of Mathematics. 16, Nr. 0, 1. Januar 1964, ISSN 1496-4279, S. 539–548. doi:10.4153/CJM-1964-055-5.
  10. Kellogg S. Booth, George S. Lueker: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. In: Journal of Computer and System Sciences. 13, Nr. 3, 1. Dezember 1976, ISSN 0022-0000, S. 335–379. doi:10.1016/S0022-0000(76)80045-1. Abgerufen am 21. November 2015.
  11. D. R. Fulkerson, O. A. Gross: Incidence matrices and interval graphs.. In: Pacific Journal of Mathematics. 15, Nr. 3, 1965, ISSN 0030-8730, S. 835–855.
  12. C. Lekkeikerker, J. Boland: Representation of a finite graph by a set of intervals on the real line. In: Fundamenta Mathematicae. 1, Nr. 51, 1962, ISSN 0016-2736, S. 45–64.