Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Graphentheorie, Äquivalenzrelation

Graphentheorie, Äquivalenzrelation

Universität / Fachhochschule

Graphentheorie

Tags: Graphentheorie

dummtrottel aktiv_icon

10:01 Uhr, 01.05.2011

Begründen Sie, ob es sich beid der folgenden Relation auf der Menger der Knoten

V

des Graphen

G = (V, E)

um eine Äquivalenzrelation handelt:

- Zwei Knoten

u, v \in V

stehen in Relation zueinander genau dann, wenn es einen Kreis in

G

gibt der beide Knoten enthält oder beide Knoten auf keinem Kreis liegen.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

tomy84

10:16 Uhr, 01.05.2011

Moin,

wo ist deine Frage:

Teste die Definition einer Äquivalenzrelation.

1.

x ~ x

trivial(liegt

x

auf einem Kreis, so liegt

x

auch auf dem Kreis)

2.

x ~ y \Leftrightarrow y ~ x

auch das ist trivial (wir wählen einen Kreis der durch

x

und

y

geht,

d . h x ~ y

offensichtlich gilt dann auch

y ~ x

dazu wählen wir einfach den selben Kreis)

3.

x ~ y

und

y ~ z \Rightarrow x ~ z

Das ist das einzige etwas trickreichere: Sei

G

der Kreis der durch

x

und

y

geht und sei

H

der Kreis durch

y

und

z

. Verbinde beide Kreise miteinander, derart, dass der Kreis

G : x - g_{1} . . g_{n - 1} - y - g_{n + 1} - ... g_{m} - x

und

H : y - h_{1} - ... h_{j - 1} - z - h_{j + 1} ... h_{i} - y

beispielhafte Wegen seien durch den Kreis (das geht immer). Dann ist

G + H := x - g_{1} ... - g_{n - 1} - y - h_{1} - ... h_{i} - y - g_{n + 1} - ... g_{m} - x

das ist wieder ein Kreis (der jetzt halt einen "Knoten" hat)

gruß

dummtrottel aktiv_icon

10:19 Uhr, 01.05.2011

Wenn es wirklich so einfach ist, ist ja ja gut. Aber ich kann im Moment nicht mehr klar denken und wollte für später, wenn ich das vielleicht wieder kann, eine Vergleichsmöglichkeit haben.

tomy84

10:33 Uhr, 01.05.2011

Hallo,

Sorry - ich nehm meinen Beweis zurück!!!

Grund: Nach Def Kreis (vgl. etwa Borkwardt Operations Research) darf jeder Punkt nur einmal durchlaufen werden.

Das heißt im allgemeinen muss es so einen Kreis der

x

und

z

enthät im 3ten Teil des Beweises nicht geben. Wir stelleun uns vor die Kreise berühren sich nur in dem Punkt

y .

Ansonsten erhältst du nur einen geschlossenen weg.

Dennoch solche Beweise verlaufen immer nach schema

f

. Alle Forderungen testen.

dummtrottel aktiv_icon

11:22 Uhr, 01.05.2011

Ergebnis meines Nachdenkversuchs:
Reflexivität und Symmetrie sollten gegeben sein.

Transitivität nicht, denn aus

u, v \in K_{1}

und

v, w \in K_{2}

folgt nicht zwingend, daß

u, w \in K_{i}

(Gegenbeispiel

z . B

. per einfacher Skizze möglich).

Richtig (Denkfähigkeit immer noch beeinträchtigt)?

tomy84

12:23 Uhr, 01.05.2011

ja genau

das ist korrekt.

Graphentheorie ist dankbarerweise gut vorstellbar.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

883166

883134

	Status: nicht eingeloggt	Noch nicht registriert?