Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.
In der Graphentheorie bezeichnet Kantenkontraktion oder Kontraktion eine grundlegende Operation auf Graphen. Dabei wird eine Kantee entfernt und die beiden anliegenden Knoten werden zu einem neuen Knoten w vereinigt.
Definition
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 .