Bei der Untersuchung von Grapheneigenschaften kommt häufiger vor dass man mit Graphen einfache ausführen also Operationen auf und zwischen Graphen muss um möglichst kompakt und damit leichter schreiben zu können. Zu diesem Zweck werden ganze Reihe von einfachen Operationen auf Graphen die häufig Anwendung finden. Dieser Artikel stellt gängigsten Operationen vor.
Eine Kante ist also genau dann Komplement eines Graphen G enthalten wenn sie nicht in G enthalten ist. Das Komplement des Komplementes G ist demnach G selbst.
Sind G 1 =( V 1 E 1 ) und G 2 =( V 2 E 2 ) Graphen des selben Typs so bezeichnet
G 1 + G 2 den Graphen der entsteht wenn man 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 aus V 2 enthalten.
Man beachte dabei die unterschiedliche Definition Begriffe Vereinigungsmenge und Differenzmenge für Mengen und Multimengen . Man schreibt auch abkürzend
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 }}) ist
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 ={{ a x }|für alle x aus V 1 \{ v w } für die { v x } oder { w x } Kante von G ist) falls G 1 Graph ohne Mehrfachkanten ist bzw.
E ({ a x }}= E 1 ({ v x }+ E 1 ({ w x }) für alle x aus V 1 \{ v w } und E ({ x y }}=0 für alle x und y aus 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 . Man nennt diese Operation Kantenkontraktion .
