matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

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
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheoriedigraph enthält kreis - beweis
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Graphentheorie" - digraph enthält kreis - beweis
digraph enthält kreis - beweis < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

digraph enthält kreis - beweis: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:53 Do 24.04.2008
Autor: die_conny

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

        
Bezug
digraph enthält kreis - beweis: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
digraph enthält kreis - beweis: Antwort
Status: (Antwort) fertig Status 
Datum: 21:06 Do 24.04.2008
Autor: Bastiane

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]

Bezug
        
Bezug
digraph enthält kreis - beweis: Antwort
Status: (Antwort) fertig Status 
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.


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


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