Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweise in der Graphentheorie richtig führen?

Beweise in der Graphentheorie richtig führen?

Universität / Fachhochschule

Graphentheorie

Tags: Graphentheorie

Komisch aktiv_icon

12:15 Uhr, 28.12.2012

Hallo,
Ich brauche Hilfe mit dem führen von Beweisen in der Graphentheorie.
Ich weiß irgendwie nicht richtig wie man an Beweise dort rangeht. Bisher habe ich es über lange Fließtexte versucht und bin mit den Ergebnissen nicht zufrieden. Deshalb würde ich mich freuen, wenn ihr mir eine bessere/andere Herangehensweise zeigen könntet. Selbst wenn meine Beweise richtig sein sollten würde ich gerne eine Variante mit mathematischen Notationen gut finden.

1) Zeige, dass wenn in

G

ein isolierter Knoten existiert, dann

\overline{G}

zusammenhängend ist.

2) Zeige, dass wenn der Graph

G

nicht zusammenhängend ist,

\overline{G}

zusammenhängend ist.

3) Gibt es Zusammenhängende Graphen

G

für die

\overline{G}

ebenfalls zusammenhängend ist? (Ich habe hier leider keine Idee wie man die Frage auch allgemein beantworten könnte und würde dies gerne erfahren. Und ja ich weiß dass es normal reicht hier ein Beispiel anzugeben.)

Bäume G=(V,E):

4) Zeige:

\forall e \in E : G \ e = (V, E \ {e})

nicht zusammenhängend

5) Zeige: Fügt man eine bel. Kante hinzu, so entsteht ein Kreis.

Beweisversuche:

1) Da ein Komplementgraph genau die Kanten enthält, die ein Graph nicht enthält sind im Komplementgraph alle Knoten des Graphen mit dem im Graphen isolierten Knoten inzident und somit ist der Graph zusammenhängend.

2) Wenn der Graph

G

nicht zusammenhängend ist, so kann man die Menge der Knoten in 2 Teilmengen aufteilen von denen keiner aus der einen Teilmenge mit einem aus der anderen Teilmenge inzident ist. Wenn man nun den Komplementgraph bildet, so bildet man an jedem Knoten der einen Menge Kanten zu jedem Knoten der anderen Menge. Somit sind nun alle Knoten der einen Menge inzident zu allen Knoten der anderen Menge. Daraus folgt, dass der Graph nun zusammenhängend ist.

3) Ja, z.B. 1-2-3-4 -> 2-4-1-3
Keine Idee für einen allgemeinen Beweis.

4) Ein Baum ist ein zusammenhängender, kreisfreier Graph(

∣ V ∣ = n; ∣ E ∣ = ∣ V ∣ - 1 = n - 1

) somit führt dass entfernen eines Kanten zu einem nicht zusammenhängenden Graphen(

∣ V ∣ = n; ∣ E ∣ = ∣ V ∣ - 1 = n - 2

).
Wie zeige ich nun, dass

∣ E ∣ = ∣ V ∣ - 1 = n - 2

einen kreisfreien nicht zusammenhängenden Graphen darstellt?

5) Ja hier habe ich garkeinen Beweisansatz. Es ist zwar klar, dass wenn man eine Kante zw. 2 Knoten einfügt und dieser Knoten bereits mit einem anderen inzident ist dann in einem zusammenhängenden Graph zwangsweise ein Kreis entsteht. Aber beweisen kann ich dies nicht.

Ich würde mich freuen wenn ihr mir im Fall von richtigen Beweisen eine Lösungsweg in mathematischer Notation angebt und bei falschen entweder den Lösungsweg erklärt oder aber mögliche Ansätze gebt so dass ich bei diesen Aufgaben weiterkomme.

MfG
ich

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

michaL aktiv_icon

12:52 Uhr, 28.12.2012

Hallo,

du könntest generell etwas formaler werden.
In 1) etwa so:
Sei

G = (V, E)

der besagte Graph und

v \in V

der/ein isolierter Knoten. Das bedeutet, dass für alle

w \in V

mit

v \neq w

die Kante

v w \notin E

gilt.
Seien nun

x, y \in V

verschieden.
Fallunterscheidung:
Fall 1:

v \in {x, y}

, etwa

v = x

. Nach oben genanntem gilt:

x y = v y \notin E \overset{}{\Leftrightarrow} v y \in \overline{E}

. Also ist

v y

ein Weg in

\overline{G}

.
Fall 2:

v \notin {x, y}

, d.h.

v, x, y

sind paarweise verschieden. Dann gelten nach Fall 1

v x, v y \in \overline{E}

, d.h.

x v y

ist ein Weg in

\overline{G}

.

Deine Formulierung wäre sozusagen die Angabe der zentralen Beweisidee.

Versuche doch einmal, 2) zu formalisieren!

Mfg Michael

Komisch aktiv_icon

23:50 Uhr, 28.12.2012

G = (V_{1} ⊎ V_{2}, E_{1} ⊎ E_{2}) \Rightarrow \overline{G} = (V_{1} ⊎ V_{2}, \overline{E})

E = E_{1} ⊎ E_{2}

\forall v \in V_{1} u n d \forall v ʹ \in V_{2} \Rightarrow v v ʹ \notin E_{1} u n d v v ʹ \notin E_{2} \overset{}{\Leftrightarrow} v v ʹ \in \overline{E_{1}} u n d v v ʹ \in \overline{E_{2}}

Daraus folgt, dass

\overline{G}

ein zusammenhängender Graph ist.

Stimmt dies so?
-------------------------------------
Wollte noch fragen wozu du die Fallunterscheidung bei 1.) machst?
Könnte man dies dann nicht auch so schreiben:

G = (V, E)

v, v ʹ \in V

d e g (v) = 0 \Rightarrow v v ʹ \notin E

\exists v \in V, \forall v ʹ \in V : v v ʹ \notin E \overset{}{\Leftrightarrow} v v ʹ \in \overline{E}

Daraus folgt, dass ein Graph G mit mindestens einem bel. isolierten Knoten ein zusammenhängender Graph

\overline{G}

folgt.

???

michaL aktiv_icon

14:33 Uhr, 29.12.2012

Hallo,

> Wollte noch fragen wozu du die Fallunterscheidung bei 1.) machst?
Dumme Antwort: Um den Beweis zu führen.

Ok, du willst darauf verzichten. Ob deine Version einem Korrektor reicht, weiß ich nicht. Letztlich geht es doch genau darum, dass der isolierte Punkt in

G

zu einer Art "Zentrum" in

\overline{G}

wird, einem Knoten, mit dem alle anderen Knoten verbunden sind.

Sicher habt ihr eine Definition dafür, wann ein Graph zusammenhängend ist, gell?
Die, an die ich mich erinnere, besagt so etwas wie: Ein Graph

G = (V, E)

heißt zusammenhängend, falls es für zwei beliebige und verschiedene Knoten

x, y \in V

einen Weg von

x

nach

y

G

gibt.

Wenn man die verwendet, muss man wohl eine Fallunterscheidung machen.

Bei der Aufgabe 2) würde ich wieder eine Fallunterscheidung machen.

Sei also

G = (V, E)

nicht zusammenhängen. Dann gibt es eine Partitionierung der Eckenmenge

V = V_{1} \overset{•}{\cup} V_{2}

V_{1}, V_{2} \neq \emptyset

. Außerdem gilt dann

x y \in E

genau dann, wenn

x, y \in V_{1}

oder

x, y \in V_{2}

.
Wenn du so willst, dann kann man auch die Kantenmenge partitionieren:

E = E_{1} \overset{•}{\cup} E_{2}

, sodass

G = (V_{1}, E_{1}) \cup (V_{2}, E_{2})

gilt. (Wenn ihr über Vereinigungsgraphen schon gesprochen habt, dann weißt du, was gemeint ist. Wenn nicht, dann google danach.)

Soweit entspricht das in etwa deiner Formalisierung, wobei die wichtigen Eigenschaften schon sehr verkürzt bei dir dargestellt sind.

Nun musst du den Übergang von

G = (V_{1}, E_{1}) \cup (V_{2}, E_{2})

\overline{G}

hinkriegen. Das bedeutet, es geht um die Kanten, was du ansatzweise auch probiert hast.
Letztlich geht es um zwei Knoten und die Existenz eines Wegs zwischen den beiden in

\overline{G}

. Hier kommt nun die Fallunterscheidung ins Spiel.
Beginne damit, dass beide Knoten aus verschiedenen Knotenmengen stammen.
Fall zwei sollte sein, dass sie aus aus der gleichen Knotenmenge (egal ob

V_{1}

oder

V_{2}

) stammen.

Die Fallunterscheidung schafft Klarheit!

Mfg Michael

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

1061031

1060878

	Status: nicht eingeloggt	Noch nicht registriert?