6  Kontraktion und Minoren

Definition 6.1

Ist \(e=xy\) eine Kante eines Graphen \(G=(V,E)\), so bezeichnet \(G/e\) den durch (Kanten-)Kontraktion von \(e\) aus \(G\) entstehenden Graphen. Dabei fassen wir \(x\) und \(y\) zu einem neuen Knoten \(v_e\) zusammen. Der Knoten \(v_e\) erhält als Nachbarn alle Knoten, die zuvor an \(x\) oder \(y\) angrenzten.

Formal sei \(G/e := (V^\prime, E^\prime)\) mit \[ V'=\bigl(V\setminus\{x,y\}\bigr)\cup\{v_e\}, \] \[ E'=\{\,vw\in E : \{v,w\}\cap\{x,y\}=\emptyset\} \;\cup\; \{\,v_e v : xv\in E\text{ oder }yv\in E\}. \]

Bemerkung

Mehrere Kontraktionen hintereinander liefern stets dasselbe Ergebnis, unabhängig von der Reihenfolge der Kanten, denn bei der Kontraktionen von \(xy\) und \(yz\):

  • Nach Kontraktion von \(xy\) muss \(v_{xy}z\) kontrahiert werden.
  • Nach Kontraktion von \(yz\) muss \(xv_{yz}\) kontrahiert werden.

Daher sind Ergbenisgraphen isomorph: \[ G/xy\;/\;v_{xy}z \;\cong\; G/yz\;/\;xv_{yz}. \]

Definition 6.2

  1. Eine Menge \(U \subseteq V\), welche einen zusammenhängenden Teilgraphen induziert, heißt Verzweigungsmenge und kann insgesamt kontrahiert werden zu einem Knoten \(v_{\text{neu}}\):

\[ G/U := (V', E') \quad \text{mit} \quad V' = V \setminus U \cup \{v_{\text{neu}}\} \]

und

\[ E' = \left\{ xy \in E \mid \{x, y\} \cap U = \emptyset \right\} \cup \left\{ v_{\text{neu}}w \mid \exists v \in U, w \in V \setminus U \text{ mit } vw \in E \right\} \]

  1. Gegeben ein weiterer Graph \(X\) und eine Familie \(\{V_x : x \in V(X)\}\) mit \(V_x \subseteq V(G)\), eine Partition von \(V(G)\) in zusammenhängende Teilmengen mit der Eigenschaft, dass \(G\) für je zwei Knoten \(x, y \in X\) genau dann eine \(V_x\)–\(V_y\)-Kante enthält, wenn \(xy \in E(X)\) ist. D.h.

\[ X = G / N_1 / N_2 / \dots / N_{|V(X)|} \]

Also kann \(X\) durch Kontraktionen von \(G\) hergeleitet werden.

  1. Mit \(\mathcal{M}X\) bezeichnen wir die Klasse aller Graphen \(G\), wofür solche Partition von X existiert. Also

\[ \mathcal{M}X := \mathcal{M}(X) : = \{G \mid X \text{ ist eine Kontraktion von } G\}. \] Manchmal schreibt man dafür auch \(IX\), wo \(I\) für „inflated“ steht.

Beispiel

  • Für \(X = (\{x_1, x_1\}, \emptyset)\) ist \(\mathcal{M}X = \{G: G\) hat genau 2 Zshgkomponente\(\}\).
  • Für Graphen \(X = \left(\{x,y\}, \{\{x,y\}\}\right)\) ist \(\mathcal{M}X = \{G: G\) Zshgkomponente, \(|G|\geq 2\}\).

Definition 6.3

Ein Graph \(G\) heißt Minor von \(H\) und wir schreiben \(G \preceq H\), wenn es einen Teilgraphen \(H' \subseteq H\) gibt, woraus \(G\) durch null oder mehrere Kontraktionen erreicht werden kann.

Definition 6.4

Ersetzen wir in einem Graphen \(X\) jede Kante \(xy \in E(X)\) durch einen \(x\)–\(y\)-Weg, sodass die Ersetzungswege keine inneren Knoten mit \(X\) oder miteinander gemeinsam haben, so nennen wir den entstandenen Graphen \(G\) eine Unterteilung von \(X\).

Wir definieren (‘T’ steht für topologisch): \[ TX := T(X) := \{ G : G \text{ ist eine Unterteilung von } X \} \] Ist \(G\) Teilgraph eines weiteren Graphen \(Y\), so heißt \(X\) topologischer Minor von \(Y\).

Die Knoten \(V(X) \subseteq V(G)\) nennen wir die Verzweigungsknoten von \(G\).
Die anderen Knoten von \(G\) (also \(V(G) \setminus V(X)\)) sind seine Unterteilungsknoten (diese Knoten haben per Definition Grad 2).

Satz 6.5

a) Jeder topologische Minor eines Graphen ist auch sein (gewöhnlicher) Minor.
\[(\text{Wenn } G \in T_X, \text{ dann } G \in \mathcal{M}_X)\]

b) Jeder Minor mit Maximalgrad \(\leq 3\) eines Graphen ist auch sein topologischer Minor.
\[ (\forall X\;\forall G\;[\,(G\in\mathcal M_X\wedge\Delta(G)\le3)\;\Rightarrow\;G\in T_X\,]) \]

Beispiel zu 6.5a

Beispiel zu 6.5b

  • Frage: \(\mathcal{M}_X = T_X\)? Nein:

Der Petersen-Graph hat \(K_5\) als Minor, aber \(K_5\) ist kein topologischer Minor.

Satz 6.6

Die Relationen

  • „\(X\) ist Minor von \(Y\)“
  • „\(X\) ist topologischer Minor von \(Y\)“

sind Ordnungsrelationen auf der Klasse der endlichen Graphen, d.h. sie sind reflexiv, transitiv und antisymmetrisch.

Beweis

Reflexiv: \(G \preceq G\) (Minor von sich selbst)

Transitiv: \(F \preceq G \text{ und } G \preceq H \Rightarrow F \preceq H\)

Antisymmetrisch: \(G \preceq H\) und \(H \preceq G \Rightarrow G \cong H\) (isomorph)

Bemerkung

Jeder induzierte Teilgraph eines Graphen ist ein Teilgraph, jeder Teilgraph ist ein topologischer Minor und jeder topologischer Minor ist ein Minor. Daher ergibt sich die strikte Verfeinerungskette der Ordnungsrelationen:

Untergraph-Relation \(\subsetneq\) Teilgraph-Relation \(\subsetneq\) topologische Minor-Relation \(\subsetneq\) Minor-Relation.

Siehe auch