Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Beweis Induktion Graph hat Zyklen
Gehe zu Seite 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 - 18:12:25    Titel: Beweis Induktion Graph hat Zyklen

Meine Frage:
Sei G = (V,E) ein ungerichteter Graph mit n > 2 Knoten. Beweisen
Sie, dass G einen Zyklus hat, falls |E| > n - 1 ist. (Hinweis: Induktion über n).

Meine Ideen:
Also ich habe mir das so gedacht:
Für einen Graph G, der nur n Knoten hat, für den gilt die IV.

IA: n=3 und somit E>n-1=2. Also hat G einen Zyklus.

Nun füge ich einen Knoten n hinzu, damit muss der neue Gesamtgraph V'=n+1 Knoten haben. Für die neue Kantenanzahl gilt dann nach der Formel |E|> n-1, dass der neue Graph mindestens (n+1)-1 Kanten haben muss, also mehr als n , also n+1 mindestens.


Die IV kann ich doch nicht hier anwenden, da diese doch erst ab 2 Knoten gilt.
für n>2

Und dann habe ich mir das jetzt so überlegt:
Ich habe den alten Graphen G1 mit n Knoten und dieser hat nach Formel mehr als n-1 Kanten (mindestens) --> also mind. n

und der neue Graph mit Knotenzufügung G2 hat mehr als n Knoten, also n+1.
=>

G2 - G1 < Anzahl der Kanten des einen zugefügten Knotens E1.
n+1 - n < E1.
E1 > 1, also mind. 2 Kanten.
kann man das so nachvollziehen?
Der neue Knoten hat nun mind. 2 Kanten, und nach IV hab ich einen Zyklus.

Nur die IV gilt erst ab einer Anzahl von 2 Knoten.
Oder kann ich das trotzdem benutzen? Confused
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8244
Wohnort: Kiel

BeitragVerfasst am: 22 Mai 2017 - 19:48:34    Titel:

Das ist alles ein wenig Kraut und Rüben. Da gehe ich nicht im Einzelnen drauf ein. Nur ein Beispiel: Die Variable n wird bei der Anzahl der Knoten und der Kanten verwendet. Und dann willst du einen Knoten hizufügen und nennst den auch n...

Formuliere als erstes einmal die zu beweisende Behauptung. Damit geht es immer los. Egal, ob der Beweis mit vollständ. Ind. erfolgt oder nicht. Denn so richtig klar ist die Behauptung da nicht formuliert, weil sie in über zwei grammatikalische Sätze verstreut ist, von denen einer die Aufgabe ("Beweisen Sie") enthält.

Also bitte: Erstmal die Behauptung.

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


Anmeldungsdatum: 22.05.2017
Beiträge: 92

BeitragVerfasst am: 22 Mai 2017 - 19:50:45    Titel:

Genau so ist die Aufgabe aber gestellt. Dass da 2x "n" vorkommt liegt daran, dass auch beides Mal die Anzahl der Knoten gemeint ist.
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8244
Wohnort: Kiel

BeitragVerfasst am: 22 Mai 2017 - 20:01:49    Titel:

Papperlapapp. Das ist vollkommen egal, ob die Aufgabe so oder anders gestellt ist.

Du hast auch nicht verstanden, was ich gemeint habe. Nämlich, dass du die Variable n in zwei Bedeutungen benutzt: Als Anzahl und als Name für einen Knoten.

Jetzt geht es um die zu beweisede Behauptung. Wie lautet die?

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


Anmeldungsdatum: 22.05.2017
Beiträge: 92

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

Die zu beweisende Behauptung lautet: G hat einen Zyklus, falls der Graph mehr Kanten hat als die Anzahl der Knoten -1.

|E|>n-1 -> G hat Zyklus.
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8244
Wohnort: Kiel

BeitragVerfasst am: 22 Mai 2017 - 20:07:48    Titel:

Nein, da fehlt was. Erstens sagst du nicht, um was für einen Graphen es sich handelt, zweitens definierst du n nicht und drittens fehlt da irgendwas mit einer Mindestzahl.

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


Anmeldungsdatum: 22.05.2017
Beiträge: 92

BeitragVerfasst am: 22 Mai 2017 - 20:08:56    Titel:

G ist ein ungerichteter Graph mit mehr als 2 Knoten: n>2.

Meinst du das?
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8244
Wohnort: Kiel

BeitragVerfasst am: 22 Mai 2017 - 20:10:28    Titel:

Und nun bitte nicht bruchstückhaft, sondern die ganze Behauptung und nichts als die Behauptung.

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


Anmeldungsdatum: 22.05.2017
Beiträge: 92

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

G ist ein ungerichteter Graph mit mehr als 2 Knoten: n>2. G hat einen Zyklus, falls die Anzahl der Kanten |E| > n-1 sind.
M_Hammer_Kruse
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 06.03.2006
Beiträge: 8244
Wohnort: Kiel

BeitragVerfasst am: 22 Mai 2017 - 20:13:34    Titel:

Was ist Ga? (P. S.: o. k., war ein Schreibfehler, hast du schon korrigiert.) Und n ist immer noch nicht definiert.

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 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12  Weiter
Seite 1 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