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.

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

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

• ${\displaystyle 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 ${\displaystyle G_{1}}$ ein Graph ohne Mehrfachkanten ist,

bzw.

• ${\displaystyle E'(\{w,x\})=E_{1}(\{u,x\})+E_{1}(\{v,x\})}$ für alle ${\displaystyle x\in V_{1}\setminus \{u,v\}}$ und ${\displaystyle E(\{x,y\})=0}$ für alle ${\displaystyle x,y\in V_{1}\{u,v\}}$, falls ${\displaystyle G_{1}}$ ein Graph mit Mehrfachkanten ist.

Man sagt, der Graph ${\displaystyle G_{2}=(V_{2},E_{2})}$ entsteht aus ${\displaystyle G_{1}}$ durch Kontraktion von e zu w, wenn ${\displaystyle V_{2}=(V_{1}\setminus \{u,v\})\cup \{w\}}$ und ${\displaystyle E_{2}=(E_{1}\setminus E)\cup E'}$.

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

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