Kantenkontraktion

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Beispiel einer Kanten­kontraktion mit den Graphen (links) und (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 | Quelltext bearbeiten]

Sei ein ungerichteter Graph, eine Kante von und w ein Knoten, der nicht zu gehört. Definiere als die Menge der Kanten zwischen den verbleibenden Knoten des Graphen und den zu entfernenden Knoten , die zum neuen Knoten umgelenkt werden, also

  • , falls ein Graph ohne Mehrfachkanten ist,

bzw.

  • für alle und für alle , falls ein Graph mit Mehrfachkanten ist.

Man sagt, der Graph entsteht aus durch Kontraktion von e zu w, falls . Es werden aus also die Knoten und alle beteiligten Kanten entfernt, und danach der neue Knoten und die umgelenkten Kanten hinzugefügt. Der Graph ist ein Minor des Graphen .