Isomorphie von Graphen

Bei der Untersuchung graphentheoretischer Probleme kommt es meist nur auf die Struktur der Graphen, nicht aber auf die Bezeichnung ihrer Knoten an. In den meisten Fällen sind die untersuchten Grapheneigenschaften dann invariant bzgl. Isomorphie, die im folgenden genauer definiert wird.

Definitionen

Seien

G_{1}

(V_{1},E_{1})

und

G_{2}

(V_{2},E_{2})

Graphen des selben Typs. Eine bijektive Abbildung

p

von

V_{1}

nach

V_{2}

heißt Isomorphismus zwischen

G_{1}

und

G_{2}

, falls gilt:

{ $v,w$ } ist Kante von $G_{1}$ genau dann, wenn { $p(v),p(w)$ } Kante von $G_{2}$ ist in ungerichteten Graphen ohne Mehrfachkanten,
$(v,w)$ ist Kante von $G_{1}$ genau dann, wenn $(p(v),p(w))$ Kante von $G_{2}$ ist in gerichteten Graphen ohne Mehrfachkanten,
$E_{1}$ ({ $v,w$ })= $E_{2}$ ({ $p(v),p(w)$ }) in ungerichteten Graphen mit Mehrfachkanten,
$E_{1}((v,w))$ = $E_{2}((p(v),p(w)))$ in gerichteten Graphen mit Mehrfachkanten,
{ $v_{1}$ ,..., $v_{k}$ } ist Kante von $G_{1}$ genau dann, wenn $\{p(v_{1})$ ,..., $p$ ( $v_{k}$ )} Kante von $G_{2}$ ist in Hypergraphen.

Zwei Graphen heißen zueinander isomorph, falls es einen Isomorphismus zwischen ihnen gibt. Die Abbildung

p

heißt Automorphismus von

G_{1}

bzw.

G_{2}

, falls zusätzlich

G_{1}

G_{2}

gilt.

Jede mathematische Formel in einem Buch halbiert die Verkaufszahl dieses Buches.

Stephen Hawking

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Isomorphie von 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