Minor (Graphentheorie)

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 den Satz von Robertson-Seymour.

Definition

Alle genannten Graphen seien stets als einfach angenommen.

Minor

Ersetzt man die Knoten $x\in V$ eines Graphen durch disjunkte zusammenhängende Graphen $G_{x}$ sowie Kanten durch $G_{x}$ - $G_{y}$ -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 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 zwei. Enthält ein Graph einen Unterteilungsgraphen eines Graphen , so nennt man einen topologischen Minor von .

Äquivalente Definitionen

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

Minor

Minorexample

Links außen ist der vollständige Graph mit drei Knoten $K_{3}$ abgebildet. Dieser entsteht durch Kantenkontraktion aus dem Graph $IK_{3}$ , der wiederum in enthalten ist. $K_{3}$ 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, $K_{3}$ ist also topologischer Minor von .

Eigenschaften

Ein $TK_{3}$ , interpretiert als $IK_{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:\Longleftrightarrow G{\text{ 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 Minors ist gerade der dem Untergraphen entsprechende Minor im Sinne der Matrizenrechnung der Adjazenzmatrix des ursprünglichen Graphen.

Basierend auf einem Artikel in:

Wikipedia.de