Umkehrabbildung eines Graphenautomorphismus ist auch homomorph

Neue Frage »

06.03.2014, 12:22	Klauf	Auf diesen Beitrag antworten »
Umkehrabbildung eines Graphenautomorphismus ist auch homomorph Meine Frage: Hallo Leute, wenn ich einen unendlichen Graphen $\begin{eqnarray} G=(V,E) \end{eqnarray}$ und einen Automorphismus auf $\begin{eqnarray} G \end{eqnarray}$ definiere. Dann ist der Automorphismus eine bijektive $\begin{eqnarray} \alpha \colon V \longrightarrow V \end{eqnarray}$ mit der Eigenschaft, dass für alle $\begin{eqnarray} v,w \in V \end{eqnarray}$ die Implikation $\begin{eqnarray} vw \in E \qquad \Longrightarrow \qquad \alpha(v)\alpha(w) \in E \end{eqnarray}$ gilt. Meine Frage nun, warum ist die Umkehrabbildung $\begin{eqnarray} \alpha^{-1} \end{eqnarray}$ auch ein Homomorphismus? Meine Ideen: Leider keine. Danke aber schonmal für eure Bemühungen.
06.03.2014, 15:05	Telperion	Auf diesen Beitrag antworten »
RE: Umkehrabbildung eines Graphenautomorphismus ist auch homomorph Hallo, wenn du weißt, dass $\begin{eqnarray} \alpha \end{eqnarray}$ ein Graphenautomorphismus ist, dann weißt du, dass für alle $\begin{eqnarray} v,w\in E \end{eqnarray}$ Knoten $\begin{eqnarray} x,y\in E \end{eqnarray}$ existieren mit $\begin{eqnarray} v=\alpha(x) \end{eqnarray}$ und $\begin{eqnarray} w=\alpha(y) \end{eqnarray}$ . Schreib einmal auf, was du eigentlich zeigen willst und benutzte das, was ich dir gerade hingeschrieben habe. Viele Grüße, Dominik
06.03.2014, 17:20	Klauf	Auf diesen Beitrag antworten »
Hey Telperion, danke für deine Antwort. Aber ich kriegs immer noch nicht hin. Warum muss denn für jede Kante $\begin{eqnarray} vw \in E \end{eqnarray}$ eine Kante $\begin{eqnarray} xy \in E \end{eqnarray}$ mit $\begin{eqnarray} \alpha(x)=v \end{eqnarray}$ und $\begin{eqnarray} \alpha(y)=w \end{eqnarray}$ . Dann wäre ich ja fertig. Aber sonst möchte ich zeigen, dass $\begin{eqnarray} \alpha^{-1}(v)\alpha^{-1}(w) \in E \end{eqnarray}$ , sofern $\begin{eqnarray} vw \in E \end{eqnarray}$ . Lannst du mir noch einen Tipp geben? LG
06.03.2014, 20:31	Telperion	Auf diesen Beitrag antworten »
Hey, der Tipp, den ich dir gegeben habe nutzt erstmal nur die Bijektivität von $\begin{eqnarray} \alpha \end{eqnarray}$ . Jezt nimm dir $\begin{eqnarray} v,w \end{eqnarray}$ benachbart. Dann existieren $\begin{eqnarray} x,y \end{eqnarray}$ aus $\begin{eqnarray} E \end{eqnarray}$ mit $\begin{eqnarray} v=\alpha(x) \end{eqnarray}$ und $\begin{eqnarray} w=\alpha(y) \end{eqnarray}$ . Also gilt $\begin{eqnarray} \alpha^{-1}(vw)=\alpha^{-1}(\alpha(x)\alpha(y)) \end{eqnarray}$ . Rechne jetzt weiter.
07.03.2014, 11:13	Klauf	Auf diesen Beitrag antworten »
Hey Telperion, danke für deine Hilfe. Aber ich denke du meinst $\begin{eqnarray} \alpha^{-1}(v)\alpha^{-1}(w)=\alpha^{-1}(\alpha(x))\alpha^{-1}(\alpha(y))=xy \end{eqnarray}$ Wenn nun $\begin{eqnarray} xy \in E \end{eqnarray}$ , dann wäre es super und ich endlich wieder glücklich^^. Aber ich seh es einfach nicht. Warum sollte jede Kante Urbild einer anderen Kanten bezüglich $\begin{eqnarray} \alpha \end{eqnarray}$ sein? LG
07.03.2014, 11:52	Elvis	Auf diesen Beitrag antworten »
Ich bin mir noch nicht ganz sicher, aber mir deucht, dass eine bijektive Abbildung $\begin{eqnarray} \alpha : V\to V \end{eqnarray}$ genau dann ein G-Homomorphismus ist, wenn $\begin{eqnarray} \varphi=(\alpha,\beta):G\to G \end{eqnarray}$ sich aus zwei bijektiven Abbildungen $\begin{eqnarray} \alpha:V\to V, \beta: E\to E \end{eqnarray}$ zusammensetzt. Allgemeiner scheint mir das sogar für Isomorphismen und nicht nur für Automorphismen richtig zu sein. Vielleicht hilft das, dein Problem zu lösen. P.S.: Stimmt leider nicht, wie das Gegenbeispiel eines Quadrats zeigt, bei dem man die Ecken fest lässt und eine Kante verschiebt.
Anzeige

07.03.2014, 13:53	Klauf	Auf diesen Beitrag antworten »
Hey Leute, ich lese gerad auf Wiki, dass ein Graph Isomorphismus eh nur über einen bijektiven Homomorphismus zwischen den Knotenmengen definiert ist, dessen Umkehrabbildung wieder die Homomorphieeugenschaft hat. Damit ist alles gut. Danke euch
07.03.2014, 17:54	Elvis	Auf diesen Beitrag antworten »
das ist gar nicht gut ... wenn das so definiert ist, dann kann das entweder bedeuten, dass es immer so ist - dann kann man das beweisen oder es kann bedeuten, dass es nicht so ist - dann kann man ein Gegenbeispiel finden was denn nun
07.03.2014, 22:27	Telperion	Auf diesen Beitrag antworten »
Hallo, es wäre durchaus sinnvoll zu verlangen, dass der Graphenhomomorphismus die Adjazenz von Knoten erhält, so wie du es in deinem ersten Beitrag geschrieben hast. Das müsste man dann imho auch für die Umkehrabbildung nachrechnen, folgt aber sofort mit meinem Tipp. Damit sieht man auch ein, dass die gegebene Definition ausreicht.

Neue Frage »

Antworten »

Umkehrabbildung eines Graphenautomorphismus ist auch homomorph

Verwandte Themen