[Graphentheorie] - Problem bei einem Beweis
-
Hi!
Mein Problem ist, dass ich nicht weiss, wie ich beweisen kann, dass alle vollständigen Graphen einer gegebenen Anzahl von Ecken isomorph sind.Vom Verständnis her erscheint mir das absolut logisch: allein "vollständiger Graph" sagt ja schon aus, dass jede Ecke mit jeder anderen Ecke verbunden ist. Deshalb ist es ja egal, wie die isomorphe Abbildung der Ecken des einen Graphen auf die des anderen ausschaut, die sich daraus ergebende Abbildung der Kanten des einen Graphen auf die des anderen wird immer wohldefiniert und bijektiv sein (d.h. die Bedingung für die "Isomorphität" (so dieses Wort existiert
) ist in jedem Fall erfüllt).Nur wie schreibe ich das Ganze formal hin?
-
Du brauchst einfach ne Abbildung zwischen den beiden Graphen die ein Isomorphismus ist.
Dazu numerierst Du die Knoten durch: e_1...e_n und e_1'...e_n'.
Die Kante zwichen e_i und e_j nennst v_ij bzw. v_ij'.Dann betrachtest Du die Abbildung f, f(e_i) = e_i', f(v_ij) = v_ij'.
Die ist klar bijektiv und jetzt mußte nur noch Nachrechnen, daß es ein Isomorphismus ist.MfG Jester
-
hmm.... sorry wenn ich grad auf'm Schlauch steh, aber:
Ok, auf die Art und Weise beweis ich, dass 2 gegebene Graphen isomorph sind. Was ich aber tun will, ist beweisen, dass _ALLE_ vollstaendigen Graphen (d.h. mehr als 2) einer gegebenen Eckenanzahl isomorph sind. Was ich nicht so recht verstehe:Dann betrachtest Du die Abbildung f, f(e_i) = e_i', f(v_ij) = v_ij'.
Die ist klar bijektiv und jetzt mußte nur noch Nachrechnen, daß es ein Isomorphismus ist.Ok, ich kann einen dieser Graphen herausgreifen und dessen Ecken mit e1, e2, ..., eN (bzw. die Kanten mit v12, v13, ... vNM) durchnummerieren.
Ich kann auch annehmen, dass eine bijekte Abbildung f existiert, die jeder Ecke meines Graphen auf Ecken jedes anderen vollständigen Graphen mit der gleichen Eckenanzahl abbildet. Aber wie zeig ich, dass durch diese Funktion auch fuer die Kanten biijektiv (bzw. ein Isomorphismus) ist?d.h.
f(v11) = v11'
fuer die Kante aus allen anderen betrachteten Graphen, die der Kante v11 aus meinem Graphen entspricht?
-
Seien X und Y vollständige Graphen mit n Ecken. Dann ist die die Menge E(X) aller Knoten von X gleichmächtig (gleichgross) zur Menge aller Knoten E(y) von Y. Es existiert also ein Isomorphismus f:E(x)->E(y).
Sei nun (a,b) eine Kante aus X. Dann sind f(a) und f(b) Knoten aus Y. Also ist, da Y vollständig ist (f(a),f(b)) ene Kante aus Y. Seien nun K(X) und K(Y) die Mengen der Kanten von X und Y. Dann ist also f(K(X)) Untermenge von K(y). Äguivalent zeigt man, dass f&-1;(K(Y)) Untermenge von K(x). Damit ist f:K(X)-K(Y) Bijektiv.
Zu zeigen ist noch, dass wenn die Kante p aus X am Knoten a liegt, dann f(p) aus Y am f(a) liegt. p liegt am Knoten a, also lässt sich p schreiben als p = (a,b), b sei dabei ein weiterer Knoten. Dann ist f(p)=f(a,b)=(f(a),f(b)).
qed
-
Blue-Tiger schrieb:
Ok, auf die Art und Weise beweis ich, dass 2 gegebene Graphen isomorph sind. Was ich aber tun will, ist beweisen, dass _ALLE_ vollstaendigen Graphen (d.h. mehr als 2) einer gegebenen Eckenanzahl isomorph sind.
Jo, genau das tust Du damit. Die "beiden" gegebenen Graphen sind nämlich beliebige vollständige Graphen. Wenn je zwei beliebige vollständige Graphen isomorph sind, dann sind sie alle isomorph.
-
Danke fuer die Antworten
