Induktionsbeweis - Dreieckige Graphen

11.04.2017, 13:46

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

smile

11.04.2017, 15:47

HAL 9000

Auf diesen Beitrag antworten »

Da steht "dreckig" statt "dreieckig". Augenzwinkern

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 $\begin{align*} |V\cap V_C|\leq 1 \end{align*}$ beim "Andocken" verzichtet:

Mit Kreis $\begin{align*} G=(\{A,B,C\},\{AB,BC,AC\}) \end{align*}$ und $\begin{align*} C = (\{A,C,D\},\{CD,AD,AC\}) \end{align*}$ entsteht durch Vereinigung das "Viereck mit einer Diagonale" $\begin{align*} G'=(\{A,B,C,D\},\{AB,BC,CD,AD,AC\}) \end{align*}$ , welches den Vierer-Kreis $\begin{align*} (\{A,B,C,D\},\{AB,BC,CD,AD\}) \end{align*}$ besitzt. Aber dieses $\begin{align*} G \end{align*}$ ist ja auch nicht dreckig, denn es gilt $\begin{align*} |V\cap V_C| = |\{A,B,C\}\cap \{A,C,D\}| = |\{A,C\}| = 2 > 1 \end{align*}$ .

11.04.2017, 20:16

Oggel

Auf diesen Beitrag antworten »

Okay das habe ich verstanden Danke smile

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

verwirrt

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. Gott

Gott

12.04.2017, 21:47

HAL 9000

Auf diesen Beitrag antworten »

Du könntest Vollständige Induktion über die Knotenzahl $\begin{align*} n \end{align*}$ deines dreckigen Graphen führen.

Induktionsanfang $\begin{align*} n=3 \end{align*}$ : Solltest du hinkriegen.

Induktionsschritt $\begin{align*} (<n)\to n \end{align*}$ :

Wir haben einen dreckigen Graphen $\begin{align*} G'=(V',E') \end{align*}$ mit $\begin{align*} |V'|=n \end{align*}$ . Dann gibt es laut Konstruktion solcher Graphen einen anderen dreckigen Graphen $\begin{align*} G=(V,E) \end{align*}$ sowie einen Dreierkreis $\begin{align*} C=(V_C,E_C) \end{align*}$ mit $\begin{align*} V'=V\cup V_C,E'=E\cup E_C \end{align*}$ sowie $\begin{align*} |V\cap V_C|\leq 1 \end{align*}$ . Offenkundig ist nun $\begin{align*} |V'| = |V\cup V_C| = |V|+|V_C|-|V\cap V_C| \end{align*}$ , was umgestellt sowie mit $\begin{align*} |V'|=n \end{align*}$ und $\begin{align*} |V_C|=3 \end{align*}$ dann

$\begin{align*} |V| = |V'|-|V_C|+|V\cap V_C| = n-3+|V\cap V_C|\leq n-2 \end{align*}$

bedeutet. Damit kann auf $\begin{align*} G=(V,E) \end{align*}$ die Induktionsvoraussetzung angewandt werden...

12.04.2017, 22:23

Oggel

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Du könntest Vollständige Induktion über die Knotenzahl $\begin{align*} n \end{align*}$ deines dreckigen Graphen führen.

Induktionsanfang $\begin{align*} n=3 \end{align*}$ : 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

verwirrt

Zitat:

Original von HAL 9000

$\begin{align*} |V| = |V'|-|V_C|+|V\cap V_C| = n-3+|V\cap V_C|\leq n-2 \end{align*}$
.

Wie kommst du auf die letzte Abschätzung? Sorry ich steh bei der Aufgabe richtig auf dem Schlauch traurig

traurig

Anzeige

13.04.2017, 08:54

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

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

Ähem, was ist über $\begin{align*} |V\cap V_C| \end{align*}$ vorausgesetzt? Richtig, $\begin{align*} |V\cap V_C|\leq 1 \end{align*}$ , 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

verwirrt

Für n=3 bleibt für G überhaupt nur die Möglichkeit eines Kreises $\begin{align*} C_3 \end{align*}$ . 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 $\begin{eqnarray*} \frac{n*(n-1)}{2} = 3 \end{eqnarray*}$ 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 »

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 $\begin{align*} {\color{red}(<n)\to n} \end{align*}$ :

Und diesen Weg habe ich ziemlich deutlich skizziert. Wenn du das ablehnst und stattdessen lieber $\begin{align*} n\to n+1 \end{align*}$ 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? verwirrt

verwirrt

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 $\begin{align*} k \end{align*}$ im Bereich $\begin{align*} 3\leq k\leq n-1 \end{align*}$ gilt (abgekürzt $\begin{align*} {\color{red}(<n)} \end{align*}$ ). Und die Induktionsbehauptung ist, dass die Behauptung auch für dreckige Graphen mit Knotenzahl $\begin{align*} {\color{red}n} \end{align*}$ gilt.

14.04.2017, 12:38

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 $\begin{eqnarray*} 3 \le k \le n-1 \end{eqnarray*}$ 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. unglücklich

unglücklich

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" ? unglücklich

unglücklich

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.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »