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 $G=(V,E)$ ein Graph. Ist ${\mathcal {I}}:=\{I_{x}\}_{x\in V}$ eine Familie von Intervallen dergestalt, dass gilt

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

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

Zwei Beispiele

Raumplanung

Eine Menge von $n\in \mathbb {N}$ Vorlesungen $V:=\{v_{1},v_{2}\dots v_{n}\}$ finden jeweils in einem Zeitintervall $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 $G:=(V,E)$ , wobei für $i\neq j$ gelte, dass $(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 $n\in \mathbb {N}$ Stoffen $S:=\{s_{1},s_{2}\dots s_{n}\}$ wäre bekannt, dass man sie bei einer Temperatur zwischen $t_{i}$ und $t_{i}'$ Grad lagern müsste ( $i\in \{1,2\dots n\}$ ). Wie viele Kühlschränke reichen aus, um alle zu lagern?

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

Ist nun $C\subseteq S$ eine Clique von $G$ , werden die Intervalle $\{T_{c}\}_{c\in C}$ aufgrund der Helly-Eigenschaft von Intervallen einen gemeinsamen Schnittpunkt $\tau _{C}$ besitzen. Ein Kühlschrank, der auf diese Temperatur $\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 $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]

G ist chordal und
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 $n\in \mathbb {N}$ keinen der unten abgebildeten Graphen ${\text{I}}$ , ${\text{II}}$ , ${\text{III}}_{n}$ , ${\text{IV}}_{n}$ oder ${\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 $n\in \mathbb {N}$ ein $P_{n}$ eingesetzt werden kann. Für die Familien ${\text{III}}_{n}$ und ${\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
$I {\displaystyle {\text{I}}}$
${\text{I}}$
$II {\displaystyle {\text{II}}}$
${\text{II}}$
$III n {\displaystyle {\text{III}}_{n}}$
${\text{III}}_{n}$
$IV n {\displaystyle {\text{IV}}_{n}}$
${\text{IV}}_{n}$
$V n {\displaystyle {\text{V}}_{n}}$
${\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.

Einzelnachweise

G. Hajös: Über eine Art von Graphen. In: Intern. Math. Nachr. 11. Jahrgang, Nr. 65, 1957.
Seymour Benzer: On the topology of the genetic fine structure. In: Proceedings of the National Academy of Sciences. 45. Jahrgang, Nr. 11, 1959, S. 1607, PMC 222769 (freier Volltext) – (englisch).
David Kendall: Incidence matrices, interval graphs and seriation in archeology. In: Pacific Journal of mathematics. 28. Jahrgang, Nr. 3, 1969, S. 565–570 (englisch, msp.org).
Clyde H. Coombs, J. E. Smith: On the detection of structure in attitudes and developmental processes. In: Psychological Review. 80. Jahrgang, Nr. 5, 1973, S. 337 (englisch, apa.org).
Jürgen Dorn: Temporal reasoning in sequence graphs. 10th National Conference on Artificial Intelligence (AAAI 92). In: AAAI-92 : proceedings / tenth National Conference on Artificial Intelligence, July 12-16, 1992. American Association for Artificial Intelligence, Menlo Park, CA 1992, S. 735–740 (englisch, aaai.org [PDF]).
Martin Charles Golumbic, Ron Shamir: Complexity and algorithms for reasoning about time: A graph-theoretic approach. In: Journal of the ACM (JACM). 40. Jahrgang, Nr. 5, 1993, S. 1108–1133 (englisch, acm.org).
Richard M. Karp: Mapping the genome: some combinatorial problems arising in molecular biology. twenty-fifth annual ACM symposium on Theory of computing. In: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. ACM, 1993, S. 278–285 (englisch, acm.org).
Martin Charles Golumbic: Algorithmic graph theory and perfect graphs. 1980 (englisch, zbmath.org).
Wen-Lian Hsu, Kuo-Hui Tsai: Linear time algorithms on circular-arc graphs. In: Information Processing Letters. 40. Jahrgang, Nr. 3, 8. November 1991, ISSN 0020-0190, S. 123–129, doi:10.1016/0020-0190(91)90165-E (englisch, sciencedirect.com).
P. C. Gilmore, A. J. Hoffman: A characterization of comparability graphs and of interval graphs. In: Canadian Journal of Mathematics. 16. Jahrgang, Nr. 0, 1. Januar 1964, ISSN 1496-4279, S. 539–548, doi:10.4153/CJM-1964-055-5 (englisch, math.ca).
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. Jahrgang, Nr. 3, 1. Dezember 1976, ISSN 0022-0000, S. 335–379, doi:10.1016/S0022-0000(76)80045-1 (englisch, sciencedirect.com [abgerufen am 21. November 2015]).
D. R. Fulkerson, O. A. Gross: Incidence matrices and interval graphs. In: Pacific Journal of Mathematics. 15. Jahrgang, Nr. 3, 1965, ISSN 0030-8730, S. 835–855 (englisch, projecteuclid.org).
C. Lekkeikerker, J. Boland: Representation of a finite graph by a set of intervals on the real line. In: Fundamenta Mathematicae. 1. Jahrgang, Nr. 51, 1962, ISSN 0016-2736, S. 45–64 (englisch, infona.pl).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] G. Hajös: Über eine Art von Graphen. In: Intern. Math. Nachr. 11. Jahrgang, Nr. 65, 1957.

[2] Seymour Benzer: On the topology of the genetic fine structure. In: Proceedings of the National Academy of Sciences. 45. Jahrgang, Nr. 11, 1959, S. 1607, PMC 222769 (freier Volltext) – (englisch).

[3] David Kendall: Incidence matrices, interval graphs and seriation in archeology. In: Pacific Journal of mathematics. 28. Jahrgang, Nr. 3, 1969, S. 565–570 (englisch, msp.org).

[4] Clyde H. Coombs, J. E. Smith: On the detection of structure in attitudes and developmental processes. In: Psychological Review. 80. Jahrgang, Nr. 5, 1973, S. 337 (englisch, apa.org).

[5] Jürgen Dorn: Temporal reasoning in sequence graphs. 10th National Conference on Artificial Intelligence (AAAI 92). In: AAAI-92 : proceedings / tenth National Conference on Artificial Intelligence, July 12-16, 1992. American Association for Artificial Intelligence, Menlo Park, CA 1992, S. 735–740 (englisch, aaai.org [PDF]).

[6] Martin Charles Golumbic, Ron Shamir: Complexity and algorithms for reasoning about time: A graph-theoretic approach. In: Journal of the ACM (JACM). 40. Jahrgang, Nr. 5, 1993, S. 1108–1133 (englisch, acm.org).

[7] Richard M. Karp: Mapping the genome: some combinatorial problems arising in molecular biology. twenty-fifth annual ACM symposium on Theory of computing. In: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. ACM, 1993, S. 278–285 (englisch, acm.org).

[8] Martin Charles Golumbic: Algorithmic graph theory and perfect graphs. 1980 (englisch, zbmath.org).

[9] Wen-Lian Hsu, Kuo-Hui Tsai: Linear time algorithms on circular-arc graphs. In: Information Processing Letters. 40. Jahrgang, Nr. 3, 8. November 1991, ISSN 0020-0190, S. 123–129, doi:10.1016/0020-0190(91)90165-E (englisch, sciencedirect.com).

[10] P. C. Gilmore, A. J. Hoffman: A characterization of comparability graphs and of interval graphs. In: Canadian Journal of Mathematics. 16. Jahrgang, Nr. 0, 1. Januar 1964, ISSN 1496-4279, S. 539–548, doi:10.4153/CJM-1964-055-5 (englisch, math.ca).

[11] 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. Jahrgang, Nr. 3, 1. Dezember 1976, ISSN 0022-0000, S. 335–379, doi:10.1016/S0022-0000(76)80045-1 (englisch, sciencedirect.com [abgerufen am 21. November 2015]).

[12] D. R. Fulkerson, O. A. Gross: Incidence matrices and interval graphs. In: Pacific Journal of Mathematics. 15. Jahrgang, Nr. 3, 1965, ISSN 0030-8730, S. 835–855 (englisch, projecteuclid.org).

[13] C. Lekkeikerker, J. Boland: Representation of a finite graph by a set of intervals on the real line. In: Fundamenta Mathematicae. 1. Jahrgang, Nr. 51, 1962, ISSN 0016-2736, S. 45–64 (englisch, infona.pl).