Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSamstag, 20. September 2014 

Operationen auf Graphen


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.

Einleitung

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.

Definitionen

Sei G 1 =( V E 1 ) ein ungerichter bzw. gerichteter Graph ohne Mehrfachkanten . Der ungerichte bzw. gerichtete Graph ohne 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 × V (im gerichteten Fall) ergibt.
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 + 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 }}) 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 .

Beispiele

kommen noch .



Bücher zum Thema Operationen auf Graphen

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Operationen_auf_Graphen.html">Operationen auf Graphen </a>