Isomorphie von Graphen

Definitionen

Seien und Graphen desselben Typs. Eine bijektive Abbildung heißt Isomorphismus zwischen G₁ und G₂ , falls gilt:

• ist Kante von G₁ genau dann, wenn {p(v),p(w)} Kante von G₂ ist in ungerichteten Graphen ohne Mehrfachkanten,
• ist Kante von G₁ genau dann, wenn (p(v),p(w)) Kante von G₂ ist in gerichteten Graphen ohne Mehrfachkanten,
• E₁({v,w})=E₂({p(v),p(w)}) in ungerichteten Graphen mit Mehrfachkanten, d. h. je zwei Ecken sind mit ebensovielen Kanten verbunden wie ihre Bildecken.
• E₁((v,w))=E₂((p(v),p(w))) in gerichteten Graphen mit Mehrfachkanten,
• {v₁,...,v_k} ist Kante von G₁ genau dann, wenn {p(v₁),...,p(v_k)} Kante von G₂ ist in Hypergraphen.

Zwei Graphen heißen zueinander isomorph, falls es einen Isomorphismus zwischen ihnen gibt. Die Abbildung p heißt Automorphismus von G₁ bzw. G₂, falls zusätzlich G₁ = G₂ gilt.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Isomorphie von Graphen aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung