www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Diskrete Mathematik" - Graph, Relation, Äuivalenzrel.
Graph, Relation, Äuivalenzrel. < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Graph, Relation, Äuivalenzrel.: Aufgabe
Status: (Frage) beantwortet Status 
Datum: 23:39 Mi 14.02.2007
Autor: Raingirl87

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

        
Bezug
Graph, Relation, Äuivalenzrel.: Antwort
Status: (Antwort) fertig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]