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: 23 Mai 2017 - 15:25:43    Titel:

Das Gegenteil lautet:

Es gibt in G' keinen Knoten v mit d(v)=1
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8241
Wohnort: Kiel

BeitragVerfasst am: 23 Mai 2017 - 15:31:32    Titel:

Richtig. Das ist als Fall 2 zu betrachten. Jedenfalls so ungefähr. Denn da ist jetzt noch ein Haken. Denn wenn es keinen Knoten mit d(v)=1 gibt, welche Werte kann d(v) dann in diesem Graphen haben?

Gruß
mike


Zuletzt bearbeitet von M_Hammer_Kruse am 23 Mai 2017 - 15:33:55, insgesamt einmal bearbeitet
9halbe
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 22.05.2017
Beiträge: 92

BeitragVerfasst am: 23 Mai 2017 - 15:33:52    Titel:

d(v) kann dann auch denn Wert 0 annehmen, und das darf ja nicht passieren, isolierte Knoten sind nicht zugelassen.
Und sonst kann d(v) einen bel. hohen Wert über 1 annehmen.
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8241
Wohnort: Kiel

BeitragVerfasst am: 23 Mai 2017 - 15:36:49    Titel:

Wieso sind isolierte Knoten verboten? Von dieser Einschränkung steht nichts in der Aufgabenstellung.

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


Anmeldungsdatum: 22.05.2017
Beiträge: 92

BeitragVerfasst am: 23 Mai 2017 - 15:37:34    Titel:

Mmh stimmt, aber die bringen uns doch nichts oder?
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8241
Wohnort: Kiel

BeitragVerfasst am: 23 Mai 2017 - 15:40:30    Titel:

Du musst sie auf jeden Fall mitbetrachten. Sonst gilt dein Beweis ja nur für Graphen ohne isolierte Knoten. Und dann kommt da nachher womöglich jemand um die Ecke und legt dir einen Graphen auf den Tisch, bei dem die Knoten und Kantenzahl so ist, wie es in der Aufgabe steht, der aber keine Zykel hat, nur weil da ein Knoten verwaist ist...

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


Anmeldungsdatum: 22.05.2017
Beiträge: 92

BeitragVerfasst am: 23 Mai 2017 - 15:42:09    Titel:

Okay, aber wo ist dann der Haken?
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8241
Wohnort: Kiel

BeitragVerfasst am: 23 Mai 2017 - 15:47:19    Titel:

Der Haken ist da, dass jetzt "kein Knoten mit d(v)=1" bedeutet "d(v)=0 oder d(v)=2,3,...". Und es ist geschickt, diese Fälle getrennt zu behandeln.

Die Graphen mit isolierten Knoten lassen sich nämlich als Abfallprodukt in Fall 1 erledigen. Dafür muss Fall 1 aber an zwei Stellen noch etwas modifiziert werden. Nämlich in der Falldefinition und beim Beseitigen des Knotens.

Worauf beschränkt sich dann also Fall 2?

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


Anmeldungsdatum: 22.05.2017
Beiträge: 92

BeitragVerfasst am: 23 Mai 2017 - 15:50:35    Titel:

Okay also die Falldefinition lautet dann:

Es gibt in G' einen Knoten v mit 0<=d(v)<=1

Und gelöscht wird nur ein Knoten mit Grad 1.

Fall 2 lautet dann: Es gibt in G' einen Knoten v mit d(v) > 1
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8241
Wohnort: Kiel

BeitragVerfasst am: 23 Mai 2017 - 15:58:13    Titel:

Gerade mit der letzten Zeile waren wir schon weiter. Das ist die Formulierung, bei der sich Fall 2 mit dem Fall 1 überschneidet.

Gruß
mike
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 9 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