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_1=(V,E_1)$ ein ungerichteter bzw. gerichteter Graph ohne Mehrfachkanten. Der ungerichtete bzw. gerichtete Graph ohne Mehrfachkanten $G_2=(V,E_2)$ heißt komplementärer Graph, Komplementgraph oder einfach nur Komplement von $G_1$, falls die Schnittmenge von $E_1$ und $E_2$ leer ist und die Vereinigungsmenge von $E_1$ und $E_2$

• 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_1=(V_1,E_1)$ und $G_2=(V_2,E_2)$ Graphen desselben Typs, so bezeichnet

• $G_1+G_2$ den Graphen, der entsteht, wenn man die Knoten- und Kantenmenge vereinigt,
• $G_1-E_2$ den Graphen, der entsteht, wenn man $E_2$ von der Kantenmenge von $G_1$ abzieht und
• $G_1-V_2$ den Graphen, der entsteht, wenn man $V_2$ von der Knotenmenge von $G_1$ abzieht und alle Kanten entfernt, die Knoten aus $V_2$ enthalten.

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

• $G_1 + E_2$, falls $V_2$ Teilmenge von $V_1$ ist,
• $G_1 + V_2$, falls $E_2$ leer oder Teilmenge von $E_1$ ist,
• $G_1+\{v,w\}$, falls $G_2 = (\{v,w\},\{\{v,w\}\})$,
• $G_1 + v$, falls $G_2 = (\{v\},\{\})$,
• $G_1 - \{v,w\}$, falls $E_2 = \{\{v,w\}\}$ und
• $G_1 - v$ falls $V_2=\{v\}$

Kantenkontraktion

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

Sei $G_1=(V_1,E_1)$ ein ungerichteter Graph, $e=\{v,w\}$ eine Kante von $G_1$ und a ein Knoten, der nicht zu $V_1$ 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_1(\{v,x\}) + E_1(\{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_1$ Graph mit Mehrfachkanten ist.

Man sagt, der Graph $G_2=(V_2,E_2)$ entsteht aus $G_1$ durch Kontraktion von e zu a, falls $G_2=G_1-\{v,w\}+a+E$. Es werden aus $G_1$ 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_2$ ist ein Minor des Graphen $G_1$.