Ungerichteter Graph/Kontraktionsgraph/Definition

Kontraktionsgraph

Es sei  ${}G=(V,E)$  ein Graph und  ${}e\in E$  eine Kante, die die Knotenpunkte ${}u$ und ${}v$ verbindet. Man nennt denjenigen Graphen mit der Knotenmenge  ${}V'=V/e$,  bei der ${}u$ und ${}v$ miteinander identifiziert werden, und bei dem die Kantenmenge ${}E'$ aus den Bildkanten zur Kontraktionsabbildung ${}V\rightarrow V/e$ besteht, den Kontraktionsgraphen zu  ${}e\in G$.  Er wird mit ${}G/e$ bezeichnet.