Operationen auf Graphen

Bei der Untersuchung von Grapheneigenschaften kommt es häufiger vor, dass man auf Graphen einfache Operationen anwenden muss, um möglichst kompakt und damit leichter verständlich schreiben zu können. Besonders häufig werden die üblichen Operationen der Mengenlehre (Vereinigung, Durchschnitt, Differenz und Komplement) auf Knoten- bzw. Kantenmengen von Graphen angewendet, sodass diese direkt auf Graphen definiert werden. Die Kantenkontraktion ist eine weitere Basisoperation.

Komplementgraph

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₂

• im ungerichteten Fall die Menge aller 2-elementigen Teilmengen von V bzw.
• im gerichteten Fall das kartesische Produkt $V\times V$

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 G selbst.

Grundlegende Operationen

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 und
• 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}}),
• G₁ + v, falls G₂ = ({v},{}),
• G₁ − {v,w}, falls E₂ = {{v,w}} und
• G₁ − v falls V₂ = {v}

Kantenkontraktion

Die Kantenkontraktion entfernt eine Kante e und vereinigt die anliegenden Knoten zu einem neuen Knoten a.

Sei G₁ = (V₁,E₁) ein ungerichteter Graph, e = {v,w} eine Kante von G₁ und a ein Knoten, der nicht zu V₁ gehört. Definiere E als die Menge der Kanten zwischen den verbleibenden Knoten des Graphen und den zu entfernenden Knoten {v,w}, die zum neuen Knoten a umgelenkt werden, also

• $E = \bigg\{ \{a,x\} \bigg| \forall_{x \in V_1 \setminus \{v,w\}} \{v,x\} \mbox{ oder } \{w,x\} \mbox{ Kante von G} \bigg\}$ falls G₁ Graph ohne Mehrfachkanten ist, bzw.
• E({a,x}) = E₁({v,x}) + E₁({w,x}) für alle $x \in V_1\{v,w\}$ und E({x,y}) = 0 für alle $x,y \in V_1\{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. Es werden aus G₁ also die Knoten {v,w} und alle beteiligten Kanten entfernt, und danach der neue Knoten a und die umgelenkten Kanten hinzugefügt. Der Graph G₂ ist ein Minor des Graphen G₁.