In der Graphentheorie sind Minoren gewisse Graphen, die sich durch Kantenkontraktion und durch Weglassen von Kanten oder Knoten aus einem anderen Graphen gewinnen lassen. Die Minorenrelation ist neben der Teilgraphenrelation und der Unterteilungsrelation eine der wichtigsten Relationen der Graphentheorie und erlaubt viele tiefgehende Sätze wie z. B. den Satz von Kuratowski oder das Minorentheorem von Robertson und Seymour.
Definition
Alle genannten Graphen seien stets als einfach angenommen.
Minor
Ersetzt man die Knoten eines Graphen durch disjunkte zusammenhängende Graphen sowie Kanten durch --Kanten, so erhält man einen neuen Graphen, der genannt wird ( für inflated). Diese Benennung leitet sich daraus her, dass durch die Ersetzung der Knoten durch Graphen der ursprüngliche Graph größer wird. Enthält nun ein Graph ein , so nennt man einen Minor von .
Topologischer Minor
Ist ein Graph, so heißt ein Graph Unterteilungsgraph von , falls er durch Unterteilung von Kanten aus hervorgegangen ist. Die Knoten von , die auch in enthalten sind, werden dann Verzweigungsknoten genannt, alle anderen Knoten heißen Unterteilungsknoten. Verzweigungsknoten erben ihren Grad aus , Unterteilungsknoten sind alle vom Grad 2. Enthält ein Graph einen Unterteilungsgraphen eines Graphen , so nennt man einen topologischen Minor von .
Äquivalente Definitionen
Folgende Definitionen finden sich auch gelegentlich in der Literatur:
- Minor
Ein Graph heißt Minor von , wenn einen Teilgraph enthält, aus dem durch Kantenkontraktion hervorgeht.
- Topologischer Minor
Ein Graph heißt topologischer Minor von , wenn einen Unterteilungsgraphen von enthält.
Beispiel
Minor
Links außen ist der vollständige Graph mit drei Knoten abgebildet. Dieser entsteht durch Kantenkontraktion aus dem Graphen , der wiederum in enthalten ist. ist also ein Minor von .
Topologischer Minor
Links außen ist der vollständige Graph mit drei Knoten, mittig ein Unterteilungsgraph abgebildet. Der Unterteilungsgraph ist aber im Graphen enthalten, ist also topologischer Minor von .
Eigenschaften
![](http://upload.wikimedia.org/wikipedia/commons/4/4f/Topminorasminor.png)
- Die Minorenrelation definiert eine Ordnungsrelation auf den endlichen Graphen, das heißt, sie ist reflexiv, transitiv und antisymmetrisch.
- Jeder Teilgraph eines Graphen ist auch ein Minor dieses Graphen.
- Jedes ist auch ein . Damit ist jeder topologische Minor auch ein gewöhnlicher Minor.
- Nicht jeder Minor ist auch ein topologischer Minor. Ein Beispiel dafür ist der Petersen-Graph mit seinem Minor .
- Die Minorenrelation definiert eine Wohlquasiordnung auf den endlichen Graphen. Dieser Satz ist auch als Minorentheorem bekannt.
- Die Determinante der Adjazenzmatrix eines Minors ist gerade der dem Teilgraphen entsprechende Minor im Sinne der Matrizenrechnung der Adjazenzmatrix des ursprünglichen Graphen.
Varianten
Topologische Minoren
Ein Graph wird als topologischer Minor eines Graphen bezeichnet, wenn ein Unterteilungsgraph von isomorph zu einem Teilgraphen von ist. Es ist leicht zu erkennen, dass jeder topologische Minor auch ein Minor ist. Die Umkehrung trifft jedoch im Allgemeinen nicht zu, gilt aber für Graphen mit einem maximalen Knotengrad von höchstens 3. Der vollständige Graph im Petersen-Graph ist ein Minor, aber kein topologischer Minor. Die topologische Minorenrelation ist keine Wohlquasiordnung auf der Menge der endlichen Graphen, und daher gilt das Minorentheorem von Robertson und Seymour nicht für topologische Minoren.[1]
Induzierte Minoren
Ein Graph wird als induzierter Minor eines Graphen bezeichnet, wenn er aus einem induzierten Teilgraphen von durch Zusammenziehen von Kanten erhalten werden kann. Ansonsten wird er -induziert und minorenfrei genannt.
Immersionsminoren
Eine Graphenoperation, die als Heben bezeichnet wird, ist zentral in einem Konzept, das als Immersion bezeichnet wird. Das Heben erfolgt an benachbarten Kanten. Bei drei Knoten und , wobei und Kanten im Graphen sind, ist das Heben von oder das Äquivalent von die Operation, die die beiden Kanten und entfernt und die Kante hinzufügt. In dem Fall, in dem bereits vorhanden war, werden die Knoten und nun durch mehr als eine Kante verbunden, und daher ist diese Operation an sich eine Multigraphenoperation.
In dem Fall, in dem ein Graph aus einem Graphen durch eine Folge von Hebeoperationen erhalten werden kann und dann ein isomorpher Teilgraph gefunden wird, sagen wir, dass ein Immersionsminor von ist. Es gibt noch eine andere Möglichkeit, die Immersionsminoren zu definieren, die äquivalent zur Hebeoperation ist. Wir sagen, dass ein Immersionsminor von ist, wenn es eine injektive Abbildung von Knoten in zu Knoten in gibt, bei denen die Bilder benachbarter Elemente von in durch kantendisjunkte Pfade verbunden sind.
Die Immersionsminoren-Relation ist eine Wohlquasiordnung auf der Menge der endlichen Graphen, und daher gilt das Minorentheorem von Robertson und Seymour für Immersionsminoren.
Beim Graphzeichnen entstehen Immersionsminoren als Planarisierungen nichtplanarer Graphen: Aus einer Zeichnung eines Graphen in der Ebene mit Kreuzungspunkten kann ein Immersionsminor gebildet werden, indem jeder Kreuzungspunkt durch einen neuen Knoten ersetzt wird, und dabei auch jede gekreuzte Kante in einen Pfad unterteilt wird. Dadurch können Zeichenmethoden für planare Graphen auf nicht planare Graphen erweitert werden.[2]
Ungerade Minoren
Eine alternative und äquivalente Definition von Minoren ist, dass ein Minor von ist, wenn die Knoten von durch eine Sammlung von knotendisjunkten Teilbäumen von dargestellt werden können, so dass, wenn zwei Knoten in benachbart sind, eine Kante mit seinen Endknoten in den entsprechenden zwei Bäumen in existiert.
Ein ungerader Minor schränkt diese Definition ein, indem diesen Teilbäumen Paritätsbedingungen hinzugefügt werden. Wenn wie oben durch eine Sammlung von Teilbäumen von dargestellt wird, ist ein ungerader Minor von , wenn es möglich ist, den Knoten von zwei Farben so zuzuweisen, dass jede Kante von innerhalb eines Teilbaums richtig gefärbt ist, denn ihre Endknoten haben unterschiedliche Farben, und jede Kante von , die eine Nachbarschaft zwischen zwei Teilbäumen darstellt, ist monochromatisch, d. h., beide Endknoten haben dieselbe Farbe. Anders als bei der üblichen Art von Minoren sind Graphen mit verbotenen ungeraden Minoren nicht unbedingt dünn.[3] Die Vermutung von Hadwiger, dass -chromatische Graphen notwendigerweise vollständige Graphen mit Knoten als Minoren enthalten, wurde auch unter dem Gesichtspunkt ungerader Minoren untersucht.[4]
Bipartite Minoren
Eine andere Erweiterung der Definition von Minoren ist das Konzept eines bipartiten Minoren, der einen bipartiten Graphen erzeugt, wenn der ursprüngliche Graph bipartit ist. Ein Graph ist ein bipartiter Minor eines anderen Graphen , wenn aus erhalten werden kann, indem Knoten entfernt, Kanten entfernt und Kantenkontraktionen durchgeführt werden, die entlang eines peripheren Zyklus des Graphen den Abstand 2 voneinander haben. Eine Form des Satzes von Wagner gilt für bipartite Minoren: Ein bipartiter Graph ist genau dann ein planarer Graph, wenn er den vollständig bipartiten Graphen nicht als bipartiten Minoren hat.[5]
Literatur
- Lutz Volkmann: Fundamente der Graphentheorie. Springer (Wien) 1996, ISBN 3-211-82774-9.
Neuere Online-Version: Graphen an allen Ecken und Kanten. (PDF; 3,5 MB). - Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (Online-Version).
Weblinks
- Eric W. Weisstein: Graph Minor. In: MathWorld (englisch).
- N. N.: Minor of a graph. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 1-55608-010-7 (englisch, encyclopediaofmath.org).
Einzelnachweise
- ↑ Guoli Ding: Excluding a long double path minor. In: Journal of Combinatorial Theory. Band 66, Nr. 1, 1996, S. 11–23, doi:10.1006/jctb.1996.0002.
- ↑ Christoph Buchheim, Markus Chimani, Carsten Gutwenger, Michael Jünger, Petra Mutzel: Handbook of Graph Drawing and Visualization. CRC Press, Boca Raton, FL 2014.
- ↑ Ken-ichi Kawarabayashi, Yusuke Kobayashi, Bruce Reed: The disjoint paths problem in quadratic time. In: Journal of Combinatorial Theory. Band 102, Nr. 2, März 2012, S. 424–435, doi:10.1016/j.jctb.2011.07.004.
- ↑ Jim Geelen, Bert Gerards, Bruce Reed, Paul Seymour, Adrian Vetta: On the odd-minor variant of Hadwiger's conjecture. In: Journal of Combinatorial Theory. Band 99, Nr. 1, 2009, S. 20–29, doi:10.1016/j.jctb.2008.03.006.
- ↑ Maria Chudnovsky, Gil Kalai, Eran Nevo, Isabella Novik, Paul Seymour: Bipartite minors. In: Journal of Combinatorial Theory. Band 116, 2016, S. 219–228, doi:10.1016/j.jctb.2015.08.001, arxiv:1312.0210.