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  x \in V eines Graphen  G durch disjunkte zusammenhängende Graphen  G_x sowie Kanten  xy durch  G_x - G_y -Kanten, so erhält man einen neuen Graphen, der  IG genannt wird ( I 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  Z ein  IG , so nennt man  G einen Minor von  Z .

Topologischer Minor[Bearbeiten | Quelltext bearbeiten]

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

Äquivalente Definitionen[Bearbeiten | Quelltext bearbeiten]

Folgende Definitionen finden sich auch gelegentlich in der Literatur:

Minor

Ein Graph  G heißt ein Minor von  Z, wenn  Z einen Teilgraph enthält, aus dem durch Kantenkontraktion  G hervorgeht.

Topologischer Minor

Ein Graph  G heißt topologischer Minor von  Z , wenn  Z einen Unterteilungsgraphen von  G enthält.

Beispiel[Bearbeiten | Quelltext bearbeiten]

Minor[Bearbeiten | Quelltext bearbeiten]

Minorexample

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

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  Z enthalten,  K_3 ist also topologischer Minor von  Z .

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

Ein  T K_3 , interpretiert als  I K_3 . Die Knoten des Unterteilungsgraphen werden den verschiedenen Graphen, welche die Knoten ersetzen, zugewiesen. Nicht jeder Knoten des  K_3 muss aber durch einen neuen Graphen ersetzt werden.
  • Die Minorenrelation  G \preccurlyeq  H:\iff G ist Minor von H 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  TX ist auch ein  IX. 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 K_5.
  • 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]