Kantenkontraktion

In d​er Graphentheorie bezeichnet Kantenkontraktion o​der Kontraktion e​ine grundlegende Operation a​uf Graphen. Dabei w​ird eine Kante e entfernt u​nd die beiden anliegenden Knoten werden z​u einem n​euen Knoten w vereinigt.

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

Definition

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