Graphentheorie < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 20:18 Mo 23.11.2009 | | Autor: | Drechen |
| Aufgabe | Sei R die Kongruenzrelation modulo 4 auf [mm] \IZ, [/mm] d.h. für a, b [mm] \in \IZgilt: [/mm]
aRb [mm] \gdw [/mm] 4|(a-b) [mm] \gdw [/mm] a hat bei Division durch 4 denselben Rest wie b.
Es wird als bekannt vorausgetzt, dass R eine Äquivalenzrelation auf [mm] \IZ [/mm] ist. Sei G der durch R definierte Graphe auf der Eckenmenge E = [mm] \{1,2,3,...,14,15\}
[/mm]
a) Seien u, v [mm] \varepsilon [/mm] E. Beweise [mm] uV_Gv\gdw [/mm] uRv
b) Sei u [mm] \in [/mm] E. Beweise [mm] Z_G(u) [/mm] = [mm] \{ v|v \in E, vRu\} [/mm] |
Ich habe einfach nur eine Frage zu meinen Beweisideen, da ich finde, dass diese eher eine Begründung als einen wirklichen Beweis darstellen.. vielleicht könnt ihr mir da ja weiterhelfen 
zu a)
Es handelt sich ja um einen Beweis in zwei Richtungen
Vor: [mm] uV_Gv\Rightarrow [/mm] Es gibt einen Weg von u nach v
zz: uRv u und v sind durch eine Kante verbunden
Beweis: Es gibt einen Weg daher [mm] u-u_1-u_2-...-v
[/mm]
da wir wissen, dass es sich um eine Äquivalenzrelation handelt kann hier die Transitivität angewandt werden und es gibt auch eine kante zwischen u und [mm] u_2 [/mm] sowie zwischen u und v.
Andere Beweisrichtung:
Vor: uRv u und v sind durch eine Kante verbunden
[mm] zz:uV_Gv\Rightarrow [/mm] Es gibt einen Weg von u nach v
Beweis (naja eher eine einfache Definition): einen Weg von u nach v bedeutet, dass man von u nach v gelangt, wobei alle Ecken paarweise verschieden sind. Da es in diesem Fall eine Kante zwischen u und v gibt, weil uRv bedeutet, dass u und v bei Teilung durch 4 denselben Rest besitzen, kann man von u nach v gelangen und da u, v verschiedene Ecken darstellen gibt ist die Kante auch ein Weg.
zu b)
wir haben einen Satz, der besagt, dass gilt
[mm] Z_G(u) [/mm] also die Zusammenhangskomponente der Ecke u
[mm] Z_G(u) [/mm] = [mm] \{ v|v \in E, vV_Gu\}
[/mm]
da wir ja auch Aufgabenteil a wissen, dass es nur eine Kante zwischen zwei Ecken gibt wenn diese auch in Relation zueinander stehen muss ja genau das zu beweisene
[mm] Z_G(u) [/mm] = [mm] \{ v|v \in E, vRu\} [/mm] gelten oder?
Sorry, vielleicht sind es wirklich blöde Fragen
Aber ich bin mir da so unsicher, weil das für mich alles keine Beweise sondern argumentative Schlüsse sind.. für Hilfe und Verbesserungen bin ich sehr dankbar, bzw. für eine wirkliche Beweisidee.... ???
Ich habe diese Frage in keinem weiteren Forum gestellt!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Fr 27.11.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
