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.