Äquivalenzrelation auf Graphen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:26 So 22.10.2006 | | Autor: | simonH06 |
| Aufgabe | | Sei G eine Menge von Graphen. Wir definieren auf G eine Relation ~ wie folgt: [mm] G_{1} [/mm] ~ [mm] G_{2} [/mm] genau dann, wenn [mm] G_{1} [/mm] und [mm] G_{2} [/mm] die Isomorphiebedingung erfüllen. Zeigen Sie, dass ~ eine Äquivalenzrelation auf G ist. |
Also, zum Lösen der Aufgabe muss man ja die Symmetrie, Reflexivität und Transitivität der Relation beweisen, oder? Nur wie Stelle ich das an? Es handelt sich ja um eine Menge von Graphen... Danke
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:35 So 22.10.2006 | | Autor: | DaMenge |
Hi,
wäre nicht schlecht, wenn du auch dazu schreibst, wann zwei Graphen bei euch isomorph heißen...
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:06 Mo 23.10.2006 | | Autor: | simonH06 |
Ok, wird gemacht:
Die Graphen [mm] G_{1}= (E_{1},K_{1},p_{1}) [/mm] und [mm] G_{2} [/mm] = [mm] (E_{2},K_{2},p_{2}) [/mm] heißen isomorph, wenn es bijektive Abbildungen [mm] \partial_{1}:\mathcal{P}(E_{1}) \to \mathcal{P}(E_{2}) [/mm] und [mm] \partial_{K}:K_{1} \to K_{2} [/mm] gibt, so dass für alle k [mm] \in K_{1} [/mm] gilt [mm] p_{2}(\partial_{K}(k))=\partial_{E}(p_{1}(k)).
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:17 Di 24.10.2006 | | Autor: | mathiash |
Hallo und guten Morgen,
ok, da verwendet jemand (Euer Dozent vermutlich) mal wieder eine Notation, die alles andere als Standard ist und die Dinge unnötig verkompliziert,
aber vielleicht mag da ja ein sich mir nicht erschließender didaktischer Hintergedanke bei sein.
Sei's drum.
Es ist also [mm] G_1=(E_1,K_1,p_1) [/mm] mit Knotenmenge [mm] E_1 [/mm] (E wie ''Ecken'', pbwohl im englischen meist V für ''vertices'' genommen wird und dann
E für die Kanten, engl. ''edges'') und Kantenmenge [mm] K_1 [/mm] und [mm] p_1\colon K_1\to P(E_1), [/mm] mit der Bedeutung e ist Knoten von k genau dann, wenn [mm] e\in p_1(k) [/mm] ist,
stimmt diese Interpretation ???
Sei das mal angenommen. Dann
- wähle zur Reflexivität (gegeben G=(E,K,p) [mm] \:\:)\:\:\: \partial_E=id_E,\partial_K=id_K
[/mm]
- für die Symmetrie gehe von [mm] \partial_E, \partial_K [/mm] zu [mm] \partial_E^{-1},\partial_K^{-1},
[/mm]
- für die Transitivität:
gegeben [mm] G_i=(E_i,K_i,p_i),\: 1\leq i\leq [/mm] 3
mit
[mm] \partial_{E,12},\partial_{K,12} [/mm] Isom. von [mm] G_1 [/mm] nach [mm] G_2, [/mm]
[mm] \partial_{E,23},\partial_{K,23} [/mm] Isom. von [mm] G_2 [/mm] nach [mm] G_3, [/mm]
dann ist [mm] \partial_{E,23}\circ\partial_{E,12}\colon E_1\to E_3, \partial_{K,23}\circ\partial_{K,12}\colon K_1\to K_3
[/mm]
ein Isom. von [mm] G_1 [/mm] nach [mm] G_3,
[/mm]
was Du natürlich nachrechnen musst.
Gruss,
Mathias
|
|
|
| |
|
Hallo und guten Morgen,
es gilt ja üblicherweise (d.h. ist definiert) [mm] G_1=(V_1,E_1)\cong G_2=(V_2,E_2) [/mm]
genau dann, wenn es [mm] f\colon V_1\to V_2 [/mm] bijektiv gibt mit
[mm] \forall u,v\in V_1\:\:\: (\: \{u,v\}\in E_1\:\Leftrightarrow\: \{f(u),f(v)\}\in E_2\:\: [/mm] )
Zum Nachweis der Reflexivität nehme man zu gegebenem G=(V,E) die Identität [mm] id:V\to [/mm] V.
Zus Symmetrie: Falls [mm] f\colon V_1\to V_2 [/mm] ein Isomorphismus von [mm] G_1=(V_1,E_1) [/mm] nach [mm] G_2=(V_2,E_2) [/mm] ist , so betrachte [mm] f^{-1}\colon V_2\to V_1.
[/mm]
Zur Transitivität: Falls [mm] G_1\cong G_2 [/mm] via [mm] f\colon V_1\to V_2 [/mm] und [mm] G_2\cong G_3 [/mm] via [mm] g\colon V_2\to V_3, [/mm] so weise für [mm] g\circ f\colon V_1\to V_3
[/mm]
die Isomorphismus-Eigenschaften nach.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:29 Mo 23.10.2006 | | Autor: | simonH06 |
Irgendwie werde ich immer noch nicht so schlau dadurch :(
|
|
|
| |
|
Siehe Mitteilung im anderen Teilstrang.
Gruss,
Mathias
|
|
|
|
