Minor (Graphentheorie)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Graphentheorie sind Minoren gewisse Graphen, die sich durch Kantenkontraktion aus einem anderen Graphen gewinnen lassen. Die Minorenrelation ist neben der Teilgraphenrelation und der Unterteilungsrelation eine der wichtigsten Relationen der Graphentheorie und erlaubt viele tiefgehenden Sätze wie z. B. den Satz von Kuratowski oder den Satz von Robertson-Seymour.

Definition[Bearbeiten | Quelltext bearbeiten]

Alle genannten Graphen seien stets als einfach angenommen.

Minor[Bearbeiten | Quelltext bearbeiten]

Ersetzt man die Ecken eines Graphen durch disjunkte zusammenhängende Graphen sowie Kanten durch -Kanten, so erhält man einen neuen Graphen, der genannt wird ( für inflated, auf Deutsch aufgeblasen. Diese Benennung leitet sich daraus her, dass durch die Ersetzung der Ecken durch Graphen der ursprüngliche Graph „größer“ wird). Enthält nun ein Graph ein , so nennt man einen Minor von .

Topologischer Minor[Bearbeiten | Quelltext bearbeiten]

Ist ein Graph und ein Unterteilungsgraph von (also ein Graph, der aus durch Kantenunterteilung hervorgeht), so nennt man auch ein (das steht für topologisch). Die Ecken von , die auch in enthalten sind, werden Verzweigungsecken genannt, alle anderen Ecken heißen Unterteilungsecken. Verzweigungsecken erben ihren Grad aus , Unterteilungsecken sind alle von Grad zwei. Enthält nun ein Graph ein , so nennt man einen topologischen Minor von .

Äquivalente Definitionen[Bearbeiten | Quelltext bearbeiten]

Folgende Definitionen finden sich auch gelegentlich in der Literatur:

Minor

Ein Graph heißt ein 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 | Quelltext bearbeiten]

Minor[Bearbeiten | Quelltext bearbeiten]

Minorexample

Links außen ist der vollständige Graph mit drei Ecken abgebildet. Dieser entsteht durch Kantenkontraktion aus dem Graph , welcher wiederum in enthalten ist. ist also ein Minor von .

Topologischer Minor[Bearbeiten | Quelltext bearbeiten]

Topominor.png

Links außen ist der vollständige Graph mit drei Ecken, mittig ein Unterteilungsgraph abgebildet. Der Unterteilungsgraph ist aber im Graphen enthalten, ist also topologischer Minor von .

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

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.
  • Die Minorenrelation ist Minor von definiert eine Ordnungsrelation auf den endlichen Graphen, das heißt, sie ist reflexiv, transitiv und antisymmetrisch (dasselbe gilt auch für die topologische Minorenrelation).
  • 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 und dessen Minor .
  • Die Minorenrelation definiert eine Wohlquasiordnung auf den endlichen Graphen. Dieser Satz ist auch als Minorentheorem bekannt.
  • Die Determinante der Adjazenzmatrix eines Minoren ist gerade der dem Untergraphen entsprechende Minor im Sinne der Matrizenrechnung der Adjazenzmatrix des ursprünglichen Graphen.

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]