Kantenkontraktion

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.

Beispiel einer Kanten­kontraktion mit den Graphen $G_{1}$ (links) und $G_{2}$ (rechts).

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. Definiere $E$ als die Menge der Kanten zwischen den verbleibenden Knoten des Graphen und den zu entfernenden Knoten $\{u,v\}$, die zum neuen Knoten $w$ umgelenkt werden, 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}\{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, falls $G_{2}=G_{1}-\{u,v\}+w+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}$.