Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Beweis Graphentheorie

Beweis Graphentheorie

Schüler Gymnasium, 11. Klassenstufe

Tags: Beweis, Graphentheorie

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
Hawaiianer

Hawaiianer aktiv_icon

13:51 Uhr, 10.01.2013

Antworten
Hallo zusammen,

ich benötige eure Hilfe bei folgendem Beweis:

Beweisen Sie: Hat jeder Knoten in einem Graphen einen Grad von mindestens 2, dann enthält der Graph
einen Kreis.

Kreis falls nur Start- und Endknoten von W identisch sind d.h. falls v1=vn und für alle i und j aus {1... n-1} gilt dass vi ≠ vj falls i ≠ j .

folgendes habe ich dazu gefunden:

Kreise in Graphen
Kreis im Graphen G=(V,E):
Teilgraph C von G, der für ein n ∈ N isomorph zu Cn ist.
(echte Kreise: isomorph zu Cn mit n ≥ 3)
Kreis C=(V ′, E′) in G=(V,E) ist eindeutig bestimmt durch
1. Menge E′ der Kanten oder
2. Folge (v1, · · · , vn, v1) der Knoten in V ′ ⊆ V.
Länge des Kreises = Anzahl der Kanten
(z.B. im Cn also n)
Satz 5.31. Jeder Graph (V,E) enthält einen Pfad mit min{gradG(a) |a ∈ V}+1 Knoten.
2. Jeder Graph (V,E) enthält einen Kreis mit mindestens min{gradG(a) |a ∈ V}+1 Knoten.


vielen Dank im Vorraus

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."
Hierzu passend bei OnlineMathe:
Online-Nachhilfe in Mathematik
Antwort
SariFari

SariFari aktiv_icon

18:34 Uhr, 10.01.2013

Antworten
Ich nehme einfach mal an, dass du vestanden hast, was ein Kreis ist.

Ich würde vielleicht versuchen, das induktiv über die Anzahl der Knoten zu zeigen.

Hattet ihr bereits den Satz, dass ein Graph zusammenhängend und kreisfrei ist genau dann, wenn er n-1 Einfachkanten hat? (n sei dabei die Anzahl der Knoten)

Ich hoffe, das reicht als kleiner Denkanstoß :-)

LG
Hawaiianer

Hawaiianer aktiv_icon

21:41 Uhr, 10.01.2013

Antworten

ja diesen Satz hatten wir bereits, jedoch hilft er mir glaube nicht weiter. weil zusammenhängend ja nicht unbedingt bedeutet das er einen Kreis besitzt.
Antwort
SariFari

SariFari aktiv_icon

07:46 Uhr, 11.01.2013

Antworten
es ging mir dabei auch weniger um das Attribut "zusammenhängend", sondern mehr darum, dass du mit Grad 2 jedes Knotens sicherlich mehr als n-1 Kanten hast.
Hawaiianer

Hawaiianer aktiv_icon

19:38 Uhr, 11.01.2013

Antworten
Ich weiß ja laut Definition, dass ein kreisfreier Graph ein Wald ist und Wälder Ecken/Knoten vom Grad ≤ 1 enthalten.

Somit muss ja bei Gard ≥2 ein Kreis existieren.

Aber das ist für eine 4 Punkte Aufgabe glaube ich unreichend bewiesen.

wie sieht ein vollständiger Beweis da aus? (vie die allgemeinheut bei ≥2)

Bei Knotengrad =2 existiert ja ein euler Kreis.

http://books.google.de/books?id=R3SzmBJBjJ4C&pg=PA166&lpg=PA166&dq=Beweis+euler+kreis&source=bl&ots=Qpq8YTwgkS&sig=OFr78rRzEpaSWLTxbDNyWFJMxjU&hl=de&sa=X&ei=wV3wUM_8GIHDtQb5iYGIBw&ved=0CEUQ6AEwBA#v=onepage&q=Beweis%20euler%20kreis&f=false

dort gibt es ja bereits einen Beweis. Ich benötige es jedoch für die allgemeinheit.
Hawaiianer

Hawaiianer aktiv_icon

19:02 Uhr, 14.01.2013

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