Kantenkontraktion

Bei der Untersuchung von Grapheneigenschaften kommt es häufiger vor, dass man mit Graphen einfache „Rechnungen“ ausführen, also Operationen auf und zwischen Graphen anwenden muss, um möglichst kompakt und damit leichter verständlich schreiben zu können. Zu diesem Zweck werden eine ganze Reihe von einfachen Operationen auf Graphen definiert, die häufig Anwendung finden. Dieser Artikel stellt die gängigsten Operationen vor.

Definitionen

Sei G₁=(V,E₁) ein ungerichteter bzw. gerichteter Graph ohne Mehrfachkanten. Der ungerichtete bzw. gerichtete Graph ohne Mehrfachkanten G₂=(V,E₂) heißt komplementärer Graph, Komplementgraph oder einfach nur Komplement von G₁, falls die Schnittmenge von E₁ und E₂ leer ist und die Vereinigungsmenge von E₁ und E₂

• die Menge aller 2-elementigen Teilmengen von V (im ungerichteten Fall) bzw.
• das kartesische Produkt V×V (im gerichteten Fall)

ergibt.

Eine Kante ist also genau dann im Komplement eines Graphen G enthalten, wenn sie nicht in G enthalten ist. Das Komplement des Komplementes von G ist demnach G selbst.

Sind G₁=(V₁,E₁) und G₂=(V₂,E₂) Graphen desselben Typs, so bezeichnet

• G₁+G₂ den Graphen, der entsteht, wenn man die Knoten- und Kantenmenge vereinigt,
• G₁-E₂ den Graphen, der entsteht, wenn man E₂ von der Kantenmenge von G₁ abzieht,
• G₁-V₂ den Graphen, der entsteht, wenn man V₂ von der Knotenmenge von G₁ abzieht und alle Kanten entfernt, die Knoten aus V₂ enthalten.

Man beachte dabei die unterschiedliche Definition der Begriffe Vereinigungsmenge und Differenzmenge für Mengen und Multimengen. Man schreibt auch abkürzend

• G₁+E₂, falls V₂ Teilmenge von V₁ ist,
• G₁+V₂, falls E₂ leer oder Teilmenge von E₁ ist,
• G₁+{v,w}, falls G₂=({v,w},{{v,w}}) ist,
• G₁+v, falls G₂=({v},{}),
• G₁-{v,w}, falls E₂={{v,w}},
• G₁-v, falls V₂={v}.

Sei G₁=(V₁,E₁) ein ungerichteter Graph, e={v,w} eine Kante von G₁ und a ein Knoten, der nicht zu V₁ gehört. Sei ferner

• E={{a,x}|für alle x aus V₁\{v,w}, für die {v,x} oder {w,x} Kante von G ist}, falls G₁ Graph ohne Mehrfachkanten ist, bzw.
• E({a,x})=E₁({v,x}+E₁({w,x}) für alle x aus V₁\{v,w} und E({x,y}}=0 für alle x und y aus V₁\{v,w}, falls G₁ Graph mit Mehrfachkanten ist.

Man sagt, der Graph G₂=(V₂,E₂) entsteht aus G₁ durch Kontraktion von e zu a, falls G₂=G₁-{v,w}+a+E. Man nennt diese Operation Kantenkontraktion.