Ungerichteter Graph/Kontraktionsgraph/Definition

Kontraktionsgraph

Es sei ein Graph und eine Kante, die die Knotenpunkte und verbindet. Man nennt denjenigen Graphen mit der Knotenmenge , bei der und miteinander identifiziert werden, und bei dem die Kantenmenge aus den Bildkanten zur Kontraktionsabbildung besteht, den Kontraktionsgraphen zu . Er wird mit bezeichnet.