Induktionsbeweis - Dreieckige Graphen

Neue Frage »

Oggel Auf diesen Beitrag antworten »
Induktionsbeweis - Dreieckige Graphen
Hi Leute smile

leider weiß ich bei dieser Aufgabe überhaupt nicht was ich machen soll. Ich kann mir auch gar nicht wirklich vorstellen wie man laut Beschreibung einen dreieckigen Graphen konstruiert.

Ich hoffe ihr könnt mir einen Denkanstoß geben um irgendwie mit der Aufgabe anzufangen.

Danke schonmal smile
HAL 9000 Auf diesen Beitrag antworten »

Da steht "dreckig" statt "dreieckig". Augenzwinkern

Es ist doch sehr genau beschrieben, wie solche dreckigen Graphen konstruiert werden. Vielleicht ein Beispiel, warum die Behauptung nicht gilt, wenn man auf die Bedingung beim "Andocken" verzichtet:

Mit Kreis und entsteht durch Vereinigung das "Viereck mit einer Diagonale" , welches den Vierer-Kreis besitzt. Aber dieses ist ja auch nicht dreckig, denn es gilt .
 
 
Oggel Auf diesen Beitrag antworten »

Okay das habe ich verstanden Danke smile

Aber ich weiß überhaupt nicht wie ich mit dem Beweis anfangen soll. Der Induktionsbeweis an sich ist mir bekannt und auch klar, aber ich kann das hier irgendwie nicht übertragen.

Für n = 1 und n = 2 ist das doch ersteinmal klar oder? Also mit 1 bzw. 2 Knoten hat der Graph maximal die Länge 3.

Brauche irgendwie einen Anfang verwirrt
Oggel Auf diesen Beitrag antworten »

also ich hab nochmal rumprobiert aber ich komme einfach nicht auf einen Anfang. Kannst du mir irgendein Tipp für den Anfang geben. Gott
HAL 9000 Auf diesen Beitrag antworten »

Du könntest Vollständige Induktion über die Knotenzahl deines dreckigen Graphen führen.


Induktionsanfang : Solltest du hinkriegen.

Induktionsschritt :

Wir haben einen dreckigen Graphen mit . Dann gibt es laut Konstruktion solcher Graphen einen anderen dreckigen Graphen sowie einen Dreierkreis mit sowie . Offenkundig ist nun , was umgestellt sowie mit und dann



bedeutet. Damit kann auf die Induktionsvoraussetzung angewandt werden...
Oggel Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Du könntest Vollständige Induktion über die Knotenzahl deines dreckigen Graphen führen.


Induktionsanfang : Solltest du hinkriegen.



Für n=3 ist ja klar, dass die Länge des Kreises 3 ist, aber wie zeige ich das formal? verwirrt

Zitat:
Original von HAL 9000



.


Wie kommst du auf die letzte Abschätzung? Sorry ich steh bei der Aufgabe richtig auf dem Schlauch traurig
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Oggel
Wie kommst du auf die letzte Abschätzung?

Ähem, was ist über vorausgesetzt? Richtig, , das kann man dort einsetzen!

Zitat:
Original von Oggel
Für n=3 ist ja klar, dass die Länge des Kreises 3 ist, aber wie zeige ich das formal? verwirrt

Für n=3 bleibt für G überhaupt nur die Möglichkeit eines Kreises . Du fragst jetzt im Ernst, wie man für einen Kreis der Länge drei nachweist, dass er ein Kreis der Länge drei ist?
Oggel Auf diesen Beitrag antworten »

Also für den Induktionsanfang muss für n=3 ja gelten, damit es ein Kreis ist, dass der Graph vollständig ist. Damit gibt es ja Kanten, also einen Kreis.

Wenn man jetzt die Induktionsvoraussetung hat, muss man ja zeigen, dass es auch für n+1 gilt. Wie macht man das in dem Fall? In den oberen Abschätzungen für n n+1 einsetzen?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Oggel
Wenn man jetzt die Induktionsvoraussetung hat, muss man ja zeigen, dass es auch für n+1 gilt.

Nun, man kann die Induktion auch anders organisieren - s.o., was du leider auch nicht gelesen hast:

Zitat:
Original von HAL 9000
Induktionsschritt :

Und diesen Weg habe ich ziemlich deutlich skizziert. Wenn du das ablehnst und stattdessen lieber bevorzugst, dann bitte, aber ohne mich.
Oggel Auf diesen Beitrag antworten »

Achsoo okay. Sorry wir haben bis jetzt immer nur Induktionsbeweis gemacht mit n+1.

Mhh aber was heißt das genau in deinem Fall? Bei n+1 ist ja klar, dass man immer einen Schritt weiter geht.

Diese Organisation von Induktionsbeweis habe ich noch nie gesehen.
Alles was kleiner n ist, wird zu n? verwirrt
HAL 9000 Auf diesen Beitrag antworten »

https://de.wikipedia.org/wiki/Vollst%C3%...Vorg.C3.A4ngern

Und nochmal im einzelnen:

Im obigen Induktionsbeweis besteht die Induktionsvoraussetzung darin, dass die Behauptung für alle dreckigen Graphen mit Knotenzahl im Bereich gilt (abgekürzt ). Und die Induktionsbehauptung ist, dass die Behauptung auch für dreckige Graphen mit Knotenzahl gilt.
Oggel Auf diesen Beitrag antworten »

Oh man unglücklich
aber wenn wir als Induktionsanfang zeigen, dass es für n=3 gilt wie kommt man darauf, dass es auch für gilt?

Btw: war mein Induktionsanfang richtig?
HAL 9000 Auf diesen Beitrag antworten »

Eine Frage, mit der du erneut beweist, dass du das Prinzip der Vollständigen Induktion nicht verstanden hast. unglücklich
Oggel Auf diesen Beitrag antworten »

Naja ich hatte bis jetzt immer nur eine andere Art von Induktionsbeweisen, wo man für den induktionsamfang zeigt, dass die Behauptung gilt und das dann für n als Voraussetzung nimmt. Dann versucht man zu zeigen, dass die Behauptung auch für n+1 gilt und es muss irgendwo die Voraussetzung eingehen.

Magst du mir die Frage trotzdem beantworten?
HAL 9000 Auf diesen Beitrag antworten »

Fragst du dort aber auch "wie kommt man drauf, dass es für n gilt" ? unglücklich
Oggel Auf diesen Beitrag antworten »

Nein natürlich nicht. Ich versteh bloß nicht wie man in diesem Fall auf die Ungleichung kommt.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »