Induktionsbeweis - Dreieckige Graphen |
11.04.2017, 13:46 | Oggel | Auf diesen Beitrag antworten » | ||||
Induktionsbeweis - Dreieckige Graphen 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 |
||||||
11.04.2017, 15:47 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Da steht "dreckig" statt "dreieckig". 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 . |
||||||
11.04.2017, 20:16 | Oggel | Auf diesen Beitrag antworten » | ||||
Okay das habe ich verstanden Danke 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 |
||||||
12.04.2017, 21:12 | 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. |
||||||
12.04.2017, 21:47 | 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... |
||||||
12.04.2017, 22:23 | Oggel | Auf diesen Beitrag antworten » | ||||
Für n=3 ist ja klar, dass die Länge des Kreises 3 ist, aber wie zeige ich das formal?
Wie kommst du auf die letzte Abschätzung? Sorry ich steh bei der Aufgabe richtig auf dem Schlauch |
||||||
Anzeige | ||||||
|
||||||
13.04.2017, 08:54 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Ähem, was ist über vorausgesetzt? Richtig, , das kann man dort einsetzen!
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? |
||||||
14.04.2017, 09:22 | 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? |
||||||
14.04.2017, 11:07 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Nun, man kann die Induktion auch anders organisieren - s.o., was du leider auch nicht gelesen hast:
Und diesen Weg habe ich ziemlich deutlich skizziert. Wenn du das ablehnst und stattdessen lieber bevorzugst, dann bitte, aber ohne mich. |
||||||
14.04.2017, 11:24 | 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? |
||||||
14.04.2017, 11:28 | 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. |
||||||
14.04.2017, 12:38 | Oggel | Auf diesen Beitrag antworten » | ||||
Oh man 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? |
||||||
14.04.2017, 14:31 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Eine Frage, mit der du erneut beweist, dass du das Prinzip der Vollständigen Induktion nicht verstanden hast. |
||||||
14.04.2017, 15:38 | 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? |
||||||
14.04.2017, 16:02 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Fragst du dort aber auch "wie kommt man drauf, dass es für n gilt" ? |
||||||
14.04.2017, 16:49 | Oggel | Auf diesen Beitrag antworten » | ||||
Nein natürlich nicht. Ich versteh bloß nicht wie man in diesem Fall auf die Ungleichung kommt. |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|