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.
Definition
Sei <math>G_1=(V_1,E_1)</math> ein ungerichteter Graph, <math>e=\{u,v\}</math> eine Kante von <math>G_1</math> und w ein Knoten, der nicht zu <math>V_1</math> gehört. Sei <math>E \subseteq E_1</math> die Menge allen Kanten, die in einem der Knoten <math>\{u,v\}</math> enden.
Bilde nun die neue Kantenmenge <math>E'</math> aus <math>E</math>, indem die Kante <math>\{u,v\}</math> entfernt und in allen anderen Kanten der Knoten <math>u</math> bzw. <math>v</math> durch den neuen Knoten <math>w</math> ersetzt wird. Entstehen dabei Mehrfachkanten, wird in einem Graphen ohne Mehrfachkanten nur eine davon beibehalten. Also:
- <math> E' = \bigg\{ \{w,x\} \bigg| \forall_{x \in V_1 \setminus \{u,v\}} \{u,x\} \mbox{ oder } \{v,x\} \mbox{ Kante von G} \bigg\}</math>, falls <math>G_1</math> ein Graph ohne Mehrfachkanten ist,
bzw.
- <math> E'(\{w,x\}) = E_1(\{u,x\}) + E_1(\{v,x\})</math> für alle <math> x \in V_1 \setminus \{u,v\}</math> und <math>E(\{x,y\})=0</math> für alle <math>x,y \in V_1\{u,v\}</math>, falls <math>G_1</math> ein Graph mit Mehrfachkanten ist.
Man sagt, der Graph <math>G_2=(V_2,E_2)</math> entsteht aus <math>G_1</math> durch Kontraktion von e zu w, wenn <math>V_2 = (V_1 \setminus \{u,v\}) \cup \{w\}</math> und <math>E_2 = (E_1 \setminus E) \cup E'</math>.
Es werden aus <math>G_1</math> also die Knoten <math>\{u,v\}</math> und alle beteiligten Kanten entfernt, und danach der neue Knoten <math>w</math> und die umgelenkten Kanten hinzugefügt. Der Graph <math>G_2</math> ist ein Minor des Graphen <math>G_1</math>.
Weblinks
- Kontraktion einer Kante. In: Spektrum Lexikon der Mathematik.
- Edge Contraction. In: Wolfram MathWorld.