Kantenkontraktion

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Beispiel einer Kanten­kontraktion mit den Graphen G_1 (links) und G_2 (rechts).

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[Bearbeiten]

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.