Operationen auf Graphen

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 ungerichter 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$ × $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$ },Unknown meta: $v,w$ ) ist,
$G_{1}$ + $v$ , falls $G_{2}$ =({ $v$ },{}),
$G_{1}$ -{ $v,w$ }, falls $E_{2}$ =Unknown meta: $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$ =Unknown meta: $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

a

, falls

G_{2}

G_{1}

v,w

a

E

. Man nennt diese Operation Kantenkontraktion.

Manche Menschen haben einen Gesichtskreis vom Radius Null und nennen ihn ihren Standpunkt.

David Hilbert

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Operationen auf Graphen aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!

Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld • Dοrfplatz 25 • 17237 Blankеnsее • Tel.: 01734332309 (Vodafone/D2) • Email: cο@maτhepedιa.dе

Datenschutzerklärung

Diskrete Mathematik

Kombinatorik
Graphentheorie
- Typen von Graphen
- Nachbarschaft und Grad
- Wege, Pfade, Zyklen und Kreise
- Isomorphie von Graphen
- Operationen auf Graphen
- Zusammenhang
- Durchlaufbarkeit von Graphen
- Färbung
- Paarungen in Graphen
- Schnitte
- Knotenüberdeckungen, Cliquen und stabile Mengen
Zahlentheorie