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 Untergraphenrelation 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]

Alle genannten Graphen seien stets als einfach angenommen.

Minor[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]

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]

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]

Minor[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]

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]

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.
  • Die Minorenrelation definiert eine Wohlquasiordnung auf den endlichen Graphen. Dieser Satz ist auch als Minorentheorem bekannt.

Literatur[Bearbeiten]

Weblinks[Bearbeiten]