 |
 |
 |
 |
 |
 |
Startseite » Forum » Sind die Graphen isomorph?
Sind die Graphen isomorph?
Universität / Fachhochschule
Tags: Graph, isomorph
 
|
  |
|---|
|
Seien G1 = (V1, E1) und G2 = (V2, E2) zwei einfache ungerichtete Graphen. Φ: V1 → V2 ist ein Graphenisomorphimus zwischen G1 und G2, falls Φ bijektiv ist und für alle v, w ∈ V1 gilt: {v, w} ∈ E1 ⇐→ {Φ(v), Φ(w)} ∈ E2. Beweise oder widerlege, dass die Graphen jeweils isomorph sind. Als Beweis reicht es hier, einen Isomorphismus anzugeben. (Dass die Abbildung tatsächlich ein Isomorphismus ist, kann man nur durch Anschauen der Bilder überprüfen.)  Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo, eine erste Hilfe: Wenn 2 Graphen isomorph sind, dann haben jeweils und denselben Eckengrad. Das hilft oft, Isomorphie auszuschließen. Gruß pwm |
 |
|
also in a) haben beide Graphen bei den Knoten den Grad 3, dh. hier ist Isomorphismus möglich? in b) hat Graph 1 bei den Knoten den Grad 3 aber Graph 2 hat Knoten mit Grad 3 oder 4 dh. in b) ist gar kein Isomorphismus möglich, da das ja bijektiv sein muss, was dann nicht erfüllt ist oder? Falls das richtig ist habe ich trotzdem das Problem den Isomorphismus bei a) zu bilden, weil ich nicht weiß wie genau |
|
|
|
bzw. ich habe Folgendes durch Probieren rausbekommen: ich nenne die Abbildung kurz f damit das leichter zum schreiben ist: f(1)=J f(2)=A f(3)=B f(4)=F f(5)=G f(6)=D f(7)=I f(8)=C f(9)=E f(10)=H |
|
|
|
Hallo, das läuft jetzt wohl auf eine Fleißaufgabe heraus: Du musst alle Kanten des einen Graphen notieren und dann testen ob die entsprechenden Paare im andere Graphe auch Kanten sind . Gruß pwm |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1546579
1546490