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'$ 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'={\bigg \{}\{w,x\}{\bigg |}\forall _{x\in V_{1}\setminus \{u,v\}}\{u,x\}{\mbox{ oder }}\{v,x\}{\mbox{ Kante von G}}{\bigg \}}$, falls $G_{1}$ ein Graph ohne Mehrfachkanten ist,

bzw.

• $E'(\{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'$.

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.