Lexikon der Mathematik: Kontraktion einer Kante
Zusammenzug einer Kante, Operation auf einer Kante k = xy in einem Graphen G, die auf folgende Art und Weise durchgeführt wird.
Die Kante k wird gelöscht, die Ecken x und y werden identifiziert, und eventuell dabei auftretende parallele Kanten werden zu einer Kante vereinigt.
Bezeichnet man den so entstandenen Graphen mit G(
und
Ist die Taillenweite g(G) ≥ 4, so ergibt sich sogar
Schreiben Sie uns!