 |
 |
 |
 |
 |
 |
Startseite » Forum » Isomorphismus, zeigen einer Äquivalenzrelation
Isomorphismus, zeigen einer Äquivalenzrelation
Universität / Fachhochschule
Graphentheorie
Tags: Äquivalenzrelation, bijektive Abbildung, Graphentheorie, Isomoprhimus
 
|
  |
|---|
|
Hallo zusammen, Wir sind angelangt bei der Graphentheorie und haben uns speziell mit Isomorphismus zwischen Graphen beschäftigt und festgelegt, dass Isomorphie eine Äquivalenzrelation auf der Menge aller endlicher Graphen ist. Nun wie zeigt man das denn? Mein erster Schritt war natürlich zu sehen was man eigentlich zu zeigen hat. Äquivalenzrelation = reflexiv, symmetrisch transitiv ; man hat also diese 3 Eigenschaften zu zeigen. Wie sähe das dann aus? Reflexiv: ist isomorph? Symmetrisch: und ist isomorph? Transitiv: ist isomorph und ist isomoorph ist isomorph? Ist das so? Falls ja habe ich wie folgt angefangen: Für alle drei Eigenschaften setze ich voraus das die Graphen isomorph sind, . . es gibt eine bijektive Funktion sodass . Reflexiv: Sei zu isomorph. und Da die Abbildung eigentlich auf sich selbst abbildet. Entsprechend müsste das glaube ich reflexiv sein, es kann ja nicht anders sein, ich weiß nur nicht wie man das korrekt zeigt. Symmetrisch: Sei zu isomorph. . . ist auch zu isomorph. und hier überlege ich wirklich, weil die bijektive Funktion zeigt doch das die Elemente eine Kante bilden und die dazugehörigen Funktionswerte ebenfalls eine Kante bilden (und andersrum), da das doch schon gilt wieso muss man dann noch zeigen, dass das symmetrisch ist. Oder habe ich da einen Denkfehler, weil ich glaube das sei zu trivial? Transitiv: Da happerts auch noch bei mir, müsste ich sowas zeigen? (nicht ganz richtig und vollständig aufgeschrieben, es geht nur ums Prinzip) Ziemlich viel Text, ziemlich viel Unsinn meinerseits, ich hoffe trotzdem jemand hilft mir. :-) |
|
 |
|
Im Prinzip richtig, nur teils falsch formuliert, wa Voraussetzung und was zu zeiogen ist. Beispielsweise "reflexiv" mit richtiger Voraussetzung (und etwas ausführlicher): Sei ein beliebiger Graph. DANN definiert die identische Abbildung einen Isomorphimsus denn aus folgt wegen sofort auch und umgekehrt. Bei der Symmetrie geht es ahlt darum, dass zur Bijektion eben, weil es eine Bijektion ist, eine Umkehrabbildung existiert. Und dass diese Umkehrung auch strukturerhaltend ist, aber das folgt im Prinzip aus der Symmetrie von "genau dann, wenn". Bei transitiv betractets du in der Tat die Abbildung und zeigst die Isomorphieeigenschaft. Auch die folgt eigentlich aus der Transitivität von "genau dann, wenn". Wie du selbst anmerkst, ist das alles inhaltlich eigentlich trivial. Das hat auch nichts wirklich mit der Struktur "Graph" zu tun, sondern lässt sich offenbar eins zu eins übertragen auf die Definition von "Isomorphie" für jede beliebige Struktur (wenn man Isomorphismus dort auf die entsprechende naheliegende Weise definiert). Die Trivialität des gnazen folgt sozusagen aus seiner Allgemeinheit :-) |
 |
|
Wenn das eigentlich immer aus dem "genau dann, wenn" folgt wie schreibe ich das dann auf, wenn es doch eigentlich quasie schon so ist. Wir also alle die solche Aufgaben ebenfalls lösen müssen, haben die Erfahrung gemacht, dass wenn eine Aufgabe zu schwer ist, das dann kaum was geht aber wenn eine Aufgabe zu leicht ist, weil sie doch eigentlich logisch ist, ist es auch sehr schwer zu zeigen, das etwas so ist. Reflexiv hab ich verstanden, ok. Bei der Symmetrie sieht man halt, das passt und andersrum auch in beiden Fällen gilt ja eben auch " ". Da weiß ich einfach nciht was man da noch groß zeigen soll, also was soll ich da jetzt hinschreiben. Bei der Tranitivität ist es änlich im Prinzip würde ich hinschrieben können (vergessen wir mal das drum herum ich mache es wieder beispielhaft): Und das ist auch schon aus der Definition gegeben mit "genau dann, wenn" und auch hier sehe ich nicht, was zu zeigen, also aufzuschreiben ist. Sorry das ich da nicht weiter komme :-) Aber trotzdem bis hierhin schonmal danke |
|
|
|
Ist ja im Prinzip richtig. Beider Transitivität würde man halt schreiben: . Es gilt nach Definition von nach Voraussetzung an nach Voraussetzung an insgesamt also . ist ein Isomorphismus |
|
|
|
Danke :-) Ok Und symmetrie? . Du sagtest etwas von strukturerhaltend, was meintest du damit? |
943700
943527