digraph enthält kreis - beweis < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Angenommen, in einem (endlichen) gerichteten Graphen D = (V,A) hat jeder Knoten v aus V einen positiven Innengrad. Zeigen Sie, dass D einen gerichteten Kreis enthält. |
Also, ich habe diesen Beweis zu führen und mir ist auch klar, dass die Aussage stimmen muss, aber ich habe Probleme, das ganze zu formulieren bzw. richtig zu "beweisen".
Ich habe bis jetzt folgenden ansatz:
Also ich weiß, dass, wenn jeder Knoten einen positiven Innengrad hat, in jeden Knoten mindestens eine Kante eingehen muss. Daher kann der Graph keine Wurzel enthalten.
Aber jetzt habe ich das Problem, dass ich mit diesen Eigenschaften noch nicht richtig klar formulieren kann, warum der digraph dann einen gerichteten Kreis enthalten muss.
Ich hätte jetzt so angefangen, vielleicht einen beliebigen Knoten zu betrachten. ich weiß nun, das in diesen eine Kante eingegangen sein muss. in den Vater des Knotens ja auch, in dessen auch usw. nun kann ich das ganze beliebig lange wiederholen, komme jedoch nie zu einem Knoten, in den keine Kante eingegangen ist. da der digraph ja aber endlich ist (ist so festgelegt), könnte ich diese argumentation zwar bis zum letzten knoten fortführen, aber dann müsste dieser letztendlich wieder mit einem knoten von den bereits betrachteten verbunden sein (durch eingehende kante), was gerade einen gerichteten kreis ergibt.
nunja, ich finde meine argumentation nur sehr schwammig und ich glaube auch nicht, dass es so gemacht werden soll.
könnte mir vielleicht jemand helfen, das ganze sauber als beweis zu formulieren oder eine andere art der argumentation zu finden?
vielen dank im voraus, die_conny
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:56 Do 24.04.2008 | | Autor: | die_conny |
hat wirklich niemand eine idee, wie ich es besser formulieren könnte? ich würde es gerne heute noch fertig machen und möchte ungern meine formulierung nehmen...
vielen dank im voraus, die_conny
|
|
|
| |
|
Hallo die_conny!
Also so ganz bekomme ich das auch nicht vernünftig hin, aber ich hätte angefangen damit, dass wir annehmen, dass in jeden Knoten mindestens eine Kante hineingeht. Dann muss es mindestens einen Knoten geben, aus dem auch mindestens eine Kante rausgeht, aber der Rest läuft fürchte ich auf das Gleiche heraus, wie du's gesagt hast.
Als "Extrembeispiel" hatte ich mir einen Graphen gedacht, der aus n Knoten besteht wobei in n-1 Knoten nur jeweils eine Kante hineingeht und aus dem n-ten Knoten kommen n-1 Kanten heraus. Dann muss natürlich auch eine Kante in diesen n-ten Knoten hineingehen, und damit hat man direkt einen Kreis. Aber das ist halt nur ein Spezialfall...
Aber hast du mal in Büchern geguckt? Da könnte so etwas auch drin stehen.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:58 Fr 25.04.2008 | | Autor: | MacMath |
Ich finde an deinem Ansatz nichts auszusetzen, du wählst eine beliebige eingehende Kannte und läufst Rückwärts, du darfst das weil in jeden Knoten eine Kannte eingeht. Wegen der Endlichkeit triffst du auf ein Element mehrmals ->Kreis.
Wenn du eine etwas weniger Konstruktive herangehensweise versuchen möchtest, könnte ich mir folgendes Schema vorstellen:
Induktion über die Anzahl der Knoten n
Induktionsanfang: 1 Knoten, in diesen geht eine Kannte, also kommt sie auch aus diesem =>Kreis.
Induktionsschritt: Falls ein Knoten existiert, aus dem keine Kannte ausgeht, folgt die Beh. auf den Graphen ohne diesen Knoten. Nach demselben Schema kannst du argumentieren wenn du nicht einen einzelnen Knoten, sondern eine echte Teilmenge von Knoten betrachtest.
Man könnte die "Nachbarschaft" des Graphen nutzen, hierbei aber den Graphen als ungerichtet ansehen. Besteht der Graph nicht aus einer einzigen Nachbarschaft, gilt die Induktionsvorraussetzung auf jeder einzelnen, denn diese lautet "gilt für alle k<n+1 ...
Habe diesen Gedanken nicht zuende gedacht, aber dürfte dein Problem lösen.
Aber ich betone nochmals: Deinen ursprünglichen konstruktiven Ansatz fand ich nicht schlecht, dein "rückwärts" laufen ist immer erlaubt, der Vater beliebig.
|
|
|
|
