Kantenkontraktion

Beispiel einer Kanten­kontraktion mit den Graphen $G_1$ (links) und $G_2$ (rechts).

In der Graphentheorie bezeichnet Kantenkontraktion oder Kontraktion eine grundlegende Operation auf Graphen. Dabei wird eine Kante e entfernt und die beiden anliegenden Knoten werden zu einem neuen Knoten w vereinigt.

Definition

Sei $G_1=(V_1,E_1)$ ein ungerichteter Graph, $e=\{u,v\}$ eine Kante von $G_1$ und w ein Knoten, der nicht zu $V_1$ gehört. Sei $E\subseteq E_1$ die Menge allen Kanten, die in einem der Knoten $\{u,v\}$ enden.

Bilde nun die neue Kantenmenge $E^{\prime }$ aus $E$, indem die Kante $\{u,v\}$ entfernt und in allen anderen Kanten der Knoten $u$ bzw. $v$ durch den neuen Knoten $w$ ersetzt wird. Entstehen dabei Mehrfachkanten, wird in einem Graphen ohne Mehrfachkanten nur eine davon beibehalten. Also:

• $E^{\prime }=\{\{w,x\}|{\mathrm{\forall }}_{x\in V_1\setminus \{u,v\}}\{u,x\}\text{ oder }\{v,x\}\text{ Kante von G}\}$, falls $G_1$ ein Graph ohne Mehrfachkanten ist,

bzw.

• $E^{\prime }(\{w,x\})=E_1(\{u,x\})+E_1(\{v,x\})$ für alle $x\in V_1\setminus \{u,v\}$ und $E(\{x,y\})=0$ für alle $x,y\in V_1\{u,v\}$, falls $G_1$ ein Graph mit Mehrfachkanten ist.

Man sagt, der Graph $G_2=(V_2,E_2)$ entsteht aus $G_1$ durch Kontraktion von e zu w, wenn $V_2=(V_1\setminus \{u,v\})\cup \{w\}$ und $E_2=(E_1\setminus E)\cup E^{\prime }$.

Es werden aus $G_1$ also die Knoten $\{u,v\}$ und alle beteiligten Kanten entfernt, und danach der neue Knoten $w$ und die umgelenkten Kanten hinzugefügt. Der Graph $G_2$ ist ein Minor des Graphen $G_1$.

Weblinks

• Kontraktion einer Kante. In: Spektrum Lexikon der Mathematik.
• Edge Contraction. In: Wolfram MathWorld.