Kantenkontraktion

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.