Graph, Relation, Äuivalenzrel. < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es sei G=(V,E) ein Graph. Wir definieren eine zweistellige Relation ~G über der Menge V durch:
x~G y <--> def. es gibt in G einen Weg, der x und y verbindet.
Beweisen Sie, dass ~G eine Äquivalenzrelation ist. |
Hallo!
Kann mir evtl. bei dieser Aufgabe helfen?
Komme damit überhaupt nicht zurecht. :(
Schreibe bald Klausur und es wurden kaum Übungsaufgaben durchgesprochen und nun sitze ich vor meinen gigantischen Lösungslücken... :(
Lg, Raingirl87
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:55 Do 15.02.2007 | | Autor: | Yuma |
Hallo Raingirl,
zunächst mal: Ich bin nicht die Idealbesetzung zur Beantwortung der Frage, weil Graphentheorie bei mir schon etwas länger zurückliegt.
Trotzdem versuch ich's mal:
Du weißt bestimmt, dass eine Äquivalenzrelation eine Relation ist, die reflexiv, symmetrisch und transitiv ist.
Zur Reflexivität: Du musst zeigen, dass [mm] $x\sim_G [/mm] x$ für alle [mm] $x\in [/mm] V$ gilt, also dass es für alle Ecken $x$ einen Weg von $x$ nach $x$ gibt.
In diesem Punkt bin ich etwas unsicher: Ist es bei einem Graphen automatisch so, dass jede Ecke zumindest mit sich selbst verbunden ist?
Zur Symmetrie: Du musst zeigen, dass wenn [mm] $x\sim_G [/mm] y$ gilt, dann auch [mm] $y\sim_G [/mm] x$ gilt, oder in Worten ausgedrückt: Wenn es einen Weg gibt, der die Ecken $x$ und $y$ miteinander verbindet, dann gibt es auch einen Weg, der $y$ und $x$ miteinander verbindet.
Offensichtlich ist das so, oder?
Zur Transitivität: Du musst zeigen, dass wenn [mm] $x\sim_G [/mm] y$ und [mm] $y\sim_G [/mm] z$ gilt, dann auch [mm] $x\sim_G [/mm] z$ gilt, oder in Worten ausgedrückt: Wenn sowohl die Ecken $x$ und $y$ als auch die Ecken $y$ und $z$ durch je einen Weg verbunden werden können, dann kann man auch die Ecken $x$ und $z$ durch einen Weg miteinander verbinden.
Auch das ist eigentlich offensichtlich: Man "addiert" einfach die beiden Wege, macht also einen "Umweg" über $y$.
Ich hoffe, ich konnte dir ein bisschen weiterhelfen!
Frag' bitte nochmal nach, wenn dir etwas unklar ist, ok? 
MFG,
Yuma
|
|
|
|
