In der Graphentheorie bezeichnet Kantenkontraktion oder Kontraktion eine grundlegende Operation auf Graphen Dabei wird eine Kante e entfernt und die beiden anliegenden Knoten werden zu einem neuen Knoten w vereinigt Beispiel einer Kanten kontraktion mit den Graphen G 1 displaystyle G 1 links und G 2 displaystyle G 2 rechts Definition BearbeitenSei G 1 V 1 E 1 displaystyle G 1 V 1 E 1 nbsp ein ungerichteter Graph e u v displaystyle e u v nbsp eine Kante von G 1 displaystyle G 1 nbsp und w ein Knoten der nicht zu V 1 displaystyle V 1 nbsp gehort Definiere E displaystyle E nbsp als die Menge der Kanten zwischen den verbleibenden Knoten des Graphen und den zu entfernenden Knoten u v displaystyle u v nbsp die zum neuen Knoten w displaystyle w nbsp umgelenkt werden also E w x x V 1 u v u x oder v x Kante von G displaystyle E bigg w x bigg forall x in V 1 setminus u v u x mbox oder v x mbox Kante von G bigg nbsp falls G 1 displaystyle G 1 nbsp ein Graph ohne Mehrfachkanten ist bzw E w x E 1 u x E 1 v x displaystyle E w x E 1 u x E 1 v x nbsp fur alle x V 1 u v displaystyle x in V 1 u v nbsp und E x y 0 displaystyle E x y 0 nbsp fur alle x y V 1 u v displaystyle x y in V 1 u v nbsp falls G 1 displaystyle G 1 nbsp ein Graph mit Mehrfachkanten ist Man sagt der Graph G 2 V 2 E 2 displaystyle G 2 V 2 E 2 nbsp entsteht aus G 1 displaystyle G 1 nbsp durch Kontraktion von e zu w falls G 2 G 1 u v w E displaystyle G 2 G 1 u v w E nbsp Es werden aus G 1 displaystyle G 1 nbsp also die Knoten u v displaystyle u v nbsp und alle beteiligten Kanten entfernt und danach der neue Knoten w displaystyle w nbsp und die umgelenkten Kanten hinzugefugt Der Graph G 2 displaystyle G 2 nbsp ist ein Minor des Graphen G 1 displaystyle G 1 nbsp Abgerufen von https de wikipedia org w index php title Kantenkontraktion amp oldid 117018359
