| |
|
| Table of contents |
|
2 Definitionen 3 Beispiele |
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.
Sei G1=(V,E1) ein ungerichter bzw. gerichteter Graph ohne Mehrfachkanten. Der ungerichte bzw. gerichtete Graph ohne Mehrfachkanten G2=(V,E2) heißt komplementärer Graph, Komplementgraph oder einfach nur Komplement von G1, falls die Schnittmenge von E1 und E2 leer ist und die Vereinigungsmenge von E1 und E2
Sind G1=(V1,E1) und G2=(V2,E2) Graphen des selben Typs, so bezeichnet
Einleitung
Definitionen
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.
Man beachte dabei die unterschiedliche Definition der Begriffe Vereinigungsmenge und Differenzmenge für Mengen und Multimengen. Man schreibt auch abkürzend
Sei G1=(V1,E1) ein ungerichteter Graph, e={v,w} eine Kante von G1 und a ein Knoten, der nicht zu V1 gehört. Sei ferner
Man sagt, der Graph G2=(V2,E2) entsteht aus G1 durch Kontraktion von e zu a, falls G2=G1-{v,w}+a+E. Man nennt diese Operation Kantenkontraktion.