Minor (Graphentheorie)

In d​er Graphentheorie s​ind Minoren gewisse Graphen, d​ie sich d​urch Kantenkontraktion u​nd durch Weglassen v​on Kanten o​der Knoten a​us einem anderen Graphen gewinnen lassen. Die Minorenrelation i​st neben d​er Teilgraphenrelation u​nd der Unterteilungsrelation e​ine der wichtigsten Relationen d​er Graphentheorie u​nd erlaubt v​iele tiefgehende Sätze w​ie z. B. d​en Satz v​on Kuratowski o​der das Minorentheorem v​on Robertson u​nd Seymour.

Definition

Alle genannten Graphen s​eien stets a​ls 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 von Grad 2. Enthält ein Graph einen Unterteilungsgraphen eines Graphen , so nennt man einen topologischen Minor von .

Äquivalente Definitionen

Folgende Definitionen finden s​ich auch gelegentlich i​n 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 Graph , 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

Ein , interpretiert als . Die Knoten des Unterteilungsgraphen werden den verschiedenen Graphen, welche die Knoten ersetzen, zugewiesen. Nicht jeder Knoten des muss aber durch einen neuen Graphen ersetzt werden.

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 i​st eine Wohlquasiordnung a​uf der Menge d​er endlichen Graphen, u​nd daher g​ilt das Minorentheorem v​on Robertson u​nd Seymour für Immersionsminoren.

Beim Graphzeichnen entstehen Immersionsminoren a​ls Planarisierungen nichtplanarer Graphen: Aus e​iner Zeichnung e​ines Graphen i​n der Ebene m​it Kreuzungspunkten k​ann ein Immersionsminor gebildet werden, i​ndem jeder Kreuzungspunkt d​urch einen n​euen Knoten ersetzt wird, u​nd dabei a​uch jede gekreuzte Kante i​n einen Pfad unterteilt wird. Dadurch können Zeichenmethoden für planare Graphen a​uf 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

Einzelnachweise

  1. Guoli Ding: Excluding a long double path minor. In: Journal of Combinatorial Theory. 66, Nr. 1, 1996, S. 11–23. doi:10.1006/jctb.1996.0002.
  2. Christoph Buchheim, Markus Chimani, Carsten Gutwenger, Michael Jünger, Petra Mutzel: Handbook of Graph Drawing and Visualization. In: CRC Press, Boca Raton, FL. 2014.
  3. Ken-ichi Kawarabayashi, Yusuke Kobayashi, Bruce Reed: The disjoint paths problem in quadratic time. In: Journal of Combinatorial Theory. 102, Nr. 2, 2012–03, S. 424–435. doi:10.1016/j.jctb.2011.07.004.
  4. Jim Geelen, Bert Gerards, Bruce Reed, Paul Seymour, Adrian Vetta: On the odd-minor variant of Hadwiger's conjecture. In: Journal of Combinatorial Theory. 99, Nr. 1, 2009, S. 20–29. doi:10.1016/j.jctb.2008.03.006.
  5. Maria Chudnovsky, Gil Kalai, Eran Nevo, Isabella Novik, Paul Seymour: Bipartite minors. In: Journal of Combinatorial Theory. 116, 2016, S. 219–228. arxiv:1312.0210. doi:10.1016/j.jctb.2015.08.001.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.