Komplementgraph

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_{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}$

• die Menge aller 2-elementigen Teilmengen von V (im ungerichteten Fall) bzw.
• das kartesische Produkt $V\times 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_{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,
• $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\}\}$,
• $G_{1}-v$ falls $V_{2}=\{v\}$

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. Sei ferner

• $E={\bigg \{}\{a,x\}{\bigg |}\forall _{a\in V_{1}\setminus \{v,x\}}\{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 Merhfachkanten 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$. Man nennt diese Operation Kantenkontraktion.