Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Beweis Induktion Graph hat Zyklen
Gehe zu Seite Zurück  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Beweis Induktion Graph hat Zyklen
 
Autor Nachricht
9halbe
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 22.05.2017
Beiträge: 92

BeitragVerfasst am: 22 Mai 2017 - 20:43:06    Titel:

Oh okay.
Ist das dann noch der Induktionsanfang? Ich kenne das so, dass man da eine Zahl hat für die man weiß, dass es stimmt.

Für die Zahl jedenfalls muss aber gelten, dass die Kantenanzahl |E| größer sein muss als i-1.
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8247
Wohnort: Kiel

BeitragVerfasst am: 22 Mai 2017 - 20:47:42    Titel:

Nein das ist nicht der Induktionsanfang. Der kommt bei einer richtig gemachten Induktion erst zum Schluss (wie das Wort "Anfang" ja ganz deutlich sagt Wink , aber das wissen viele Professoren auch nicht. Die stellen dann den Induktionsanfang an den Anfang, wo er gar nicht hingehört...)

Aber meine Frage ist noch nicht beantwortet: Was gilt denn nun für i? Welches |E| soll da größer sein und größer als was?
Ähnlich wie bei der Formulierung der Behauptung musst du jetzt sauber und vollständig formuliern, was für die Zahl i gilt.

Gruß
mike
9halbe
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 22.05.2017
Beiträge: 92

BeitragVerfasst am: 22 Mai 2017 - 20:54:24    Titel:

Oh okay, ja das haben wir dann echt immer falsch gemacht.

Für die Zahl i soll doch jetzt die Behauptung gelten.
Also: bei gegebener Anzahl von i Knoten entsteht bei einer Anzahl von i-1 Kanten ein Zyklus.

So?
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8247
Wohnort: Kiel

BeitragVerfasst am: 22 Mai 2017 - 20:57:04    Titel:

Ja, in etwa. Besser kannst du das sogar genauso formulieren, wie in der Behauptung. Also nix mit da entsteht was, sondern im selben Wortlaut.

Denn du willst ja gerade sagen, dass die Behauptung für die feste Zahl i gilt.

Gruß
mike
9halbe
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 22.05.2017
Beiträge: 92

BeitragVerfasst am: 22 Mai 2017 - 20:59:25    Titel:

Also gut:

G ist ein ungerichteter Graph mit i Knoten. G hat einen Zyklus, falls die Anzahl der Kanten |E| > i-1 sind.

So?
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8247
Wohnort: Kiel

BeitragVerfasst am: 22 Mai 2017 - 21:04:39    Titel:

Genau. Und jetzt gehst du davon aus, dass dies für dein festes i gilt. Du machst das zur Voraussetzung für das Weitere, obwohl es nicht bewiesen ist und du es nur annimmst, dass es so ein i gibt.

Genau die Aussage, die du eben gemacht hast, die ist die Induktionsvoraussetzung.

Die Induktionsvoraussetzung ist also wortgleich mit der Behauptung. Nur dass die Behauptung für unendlich viele Werte von n gelten soll und die Voraussetzung nur für einen festen Wert i als Annahme gilt.

o. k.?

Gruß
mike
9halbe
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 22.05.2017
Beiträge: 92

BeitragVerfasst am: 22 Mai 2017 - 21:07:17    Titel:

Okay, ja habe ich verstanden.

Also:

IV: G ist ein ungerichteter Graph mit i Knoten. G hat einen Zyklus, falls die Anzahl der Kanten |E| > i-1 sind.

Und jetzt kommt der Induktionssatz oder?
IS: n->n+1
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8247
Wohnort: Kiel

BeitragVerfasst am: 22 Mai 2017 - 21:15:06    Titel:

Richtig. Das Ding heißt aber Induktionsschritt.

Bisher war alles formal: Behauptung sauber formulieren, daraus die Ind.-Vor. herleiten. Jetzt wird es inhaltlich. Nun musst du zeigen, dass die Behauptung, wenn sie denn für i gilt, dass sie das dann auch für i+1 tut.

Hinweis: Ganz sauber waren Behauptung und Voraussetzung noch immer nicht formuliert. Das heißt es immer nur: "G ist ein ungerichteter Graph ..."
Besser wäre noch eine Formulierung: "Für jeden ungerichteten Graphen mit soundsovielen Knoten gilt: ..." Denn du wirst gleich merken, dass du die Ind.-Vor. in dieser Form brauchst, nämlich, dass sie für alle Graphen gilt und nicht nur für irgendeinen.

So, nun bist du dran: Wenn es für i Knoten gilt, tut es dann auch für i+1? Und wenn ja, warum?

Gruß
mike
9halbe
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 22.05.2017
Beiträge: 92

BeitragVerfasst am: 22 Mai 2017 - 21:20:09    Titel:

Gut.

IV: G ist ein ungerichteter Graph mit i Knoten. G hat einen Zyklus, falls die Anzahl der Kanten |E| > i-1 sind.

Neu:
Induktionsschritt: Wir konstruieren jetzt also einen neuen Graph G'=(V',E') mit i+1 Knoten.

Kannst du einen Tipp geben, warum das stimmt?
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8247
Wohnort: Kiel

BeitragVerfasst am: 22 Mai 2017 - 21:26:12    Titel:

Nicht nur mit i+1 Knoten, sondern auch mit einer bestimmten Kantenzahl.

Übrigens taucht bei dir hier V' als Bezeichnung für die Menge der Kanten zum ersten mal auf. Hast du bisher nicht gebraucht und wirst du auch nicht. Aber wenn du Vs verwendest, dann solltes tdu es stringent von Anfang an machen, also schon in der Behauptung.

Der Induktionsschritt beginnt also mit: "Sei G' ... mit ... Knoten und ... Kanten." Formuliere das mal aus.

Gruß
mike

P. S. und in der Ind.-Vor. besser: "G ist ein beliebiger ungerichteter Graph..." Dann ist darin enthlten, dass die Voraussetzung für alle diese Graphen gilt. Das meinte ich mit 'du wirst es gleich brauchen'.


Zuletzt bearbeitet von M_Hammer_Kruse am 22 Mai 2017 - 21:29:22, insgesamt einmal bearbeitet
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Beweis Induktion Graph hat Zyklen
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite Zurück  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12  Weiter
Seite 3 von 12

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum