Operationen auf Graphen

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 G1 = (V,E1) ein ungerichteter bzw. gerichteter Graph ohne Mehrfachkanten. Der ungerichtete 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

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 G1 = (V1,E1) und G2 = (V2,E2) Graphen desselben Typs, so bezeichnet

  • G1 + G2 den Graphen, der entsteht, wenn man die Knoten- und Kantenmenge vereinigt,
  • G1E2 den Graphen, der entsteht, wenn man E2 von der Kantenmenge von G1 abzieht und
  • G1V2 den Graphen, der entsteht, wenn man V2 von der Knotenmenge von G1 abzieht und alle Kanten entfernt, die Knoten aus V2 enthalten.

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

  • G1 + E2, falls V2 Teilmenge von V1 ist,
  • G1 + V2, falls E2 leer oder Teilmenge von E1 ist,
  • G1 + {v,w}, falls G2 = ({v,w},{{v,w}}),
  • G1 + v, falls G2 = ({v},{}),
  • G1 − {v,w}, falls E2 = {{v,w}} und
  • G1v falls V2 = {v}

Kantenkontraktion

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

Sei G1 = (V1,E1) ein ungerichteter Graph, e = {v,w} eine Kante von G1 und a ein Knoten, der nicht zu V1 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 G1 Graph ohne Mehrfachkanten ist, bzw.
  • E({a,x}) = E1({v,x}) + E1({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 G1 Graph mit Mehrfachkanten ist.

Man sagt, der Graph G2 = (V2,E2) entsteht aus G1 durch Kontraktion von e zu a, falls G2 = G1 − {v,w} + a + E. Es werden aus G1 also die Knoten {v,w} und alle beteiligten Kanten entfernt, und danach der neue Knoten a und die umgelenkten Kanten hinzugefügt. Der Graph G2 ist ein Minor des Graphen G1.


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Kantenkontraktion — 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… …   Deutsch Wikipedia

  • 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… …   Deutsch Wikipedia

  • Komplementärer Graph — 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… …   Deutsch Wikipedia

  • Graphentheorie — Ungerichteter Graph mit sechs Knoten. Die Graphentheorie ist ein Teilgebiet der Mathematik, das die Eigenschaften von Graphen und ihre Beziehungen zueinander untersucht. Dadurch, dass einerseits viele algorithmische Probleme auf Graphen… …   Deutsch Wikipedia

  • Datenstruktur — In der Informatik ist eine Datenstruktur ein mathematisches Objekt zur Speicherung von Daten. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre… …   Deutsch Wikipedia

  • Datenstrukturen — In der Informatik ist eine Datenstruktur ein mathematisches Objekt zur Speicherung von Daten. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre… …   Deutsch Wikipedia

  • Cliquenweite — Die Cliquenweite ist ein Begriff aus der Graphentheorie und ordnet jedem ungerichteten Graphen     eine natürliche Zahl zu. Sie ist daher ein Graphparameter. Auf Graphen mit beschränkter Cliquenweite lassen sich viele NP vollständige… …   Deutsch Wikipedia

  • Graphdatenbank — Dieser Artikel wurde auf den Seiten der Qualitätssicherung eingetragen. Bitte hilf mit, ihn zu verbessern, und beteilige dich bitte an der Diskussion! Folgendes muss noch verbessert werden: In dieser Form ist das leider kein Artikel sondern… …   Deutsch Wikipedia

  • Flüsse und Schnitte in Netzwerken — sind Strukturen der Graphentheorie, die vielfältige Anwendungen finden. Inhaltsverzeichnis 1 Definitionen, wichtige Begriffe und Eigenschaften 1.1 Netzwerk 1.2 Fluss 1.2.1 …   Deutsch Wikipedia

  • Konkatenation (Formale Sprache) — Die Artikel Formale Sprache, Formales System, Formales System (Logik) und Kalkül überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”