Minor (Graphentheorie)

gewisse Graphen, die sich durch Kantenkontraktion und durch Weglassen von Kanten oder Knoten aus einem anderen Graphen gewinnen lassen

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

Bearbeiten

Alle genannten Graphen seien stets als einfach angenommen.

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

 

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

Bearbeiten

 

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

Bearbeiten
 
Ein  , interpretiert als  . Die Knoten des Unterteilungs­graphen werden den Graphen, die Knoten ersetzen, zugewiesen. Nicht jeder Knoten des   muss aber durch einen neuen Graphen ersetzt werden.

Varianten

Bearbeiten

Topologische Minoren

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten
Bearbeiten

Einzelnachweise

Bearbeiten
  1. 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.
  2. Christoph Buchheim, Markus Chimani, Carsten Gutwenger, Michael Jünger, Petra Mutzel: Handbook of Graph Drawing and Visualization. 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. Band 102, Nr. 2, März 2012, 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. Band 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. Band 116, 2016, S. 219–228, doi:10.1016/j.jctb.2015.08.001, arxiv:1312.0210.