Induktionsbeweise GraphTheo < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:37 Fr 25.07.2014 | | Autor: | Morgyr |
| Aufgabe | Beweise: Wenn ein Baum genau [mm] k\ge1 [/mm] Knoten vom Grad 4 enthält,
dann besitzt der Baum mindestens 2k + 2 Blätter. |
Das ganze über Induktion nach k.
Induktionsverankerung
Der Baum hat genau 1 Knoten k mit deg(k) > 1, bzw. deg(k)=4
Entsprechend hat der dieser Knoten genau 4 Knoten x mit deg(x)=1, also 4 Blätter.
Also Bedingung erfüllt: 2*1+2 = deg(k)
Induktionsannahme
x Knoten k mit deg(k) = 4 und 0 Knoten j mit 1 < deg(j) < 4.
Wenn zweite Bedingung nicht erfüllt, also bspw. 1 deg(j) = 2, so ändert sich nichts an der Anzahl Blätter. Da es sich um einen Baum handelt, geht von einem 4er Grad eine Verbindung zum 2er, der 2er hat dann 1 Blatt, wodurch die Anzahl der Blätter in Relation zu 4er Grad konstant ist. Im Fall 1 deg(j) = 3 entsteht sogar ein Blatt mehr, dies ist aber nicht relevant, da 2 *k + 2 die minimale Grenze ist.
Damit Kreisfreiheit und Zusammenhang für den Baum erfüllt ist, gibt es zwischen den 4er Knoten immer 1 Verbindung. Entsprechend (k-1) Verbindungen zu nicht-Blätter. Die Knoten k, für die das zu trifft, haben deg(k) = 4, dementsprechend gibt es
4k - (k-1) Verbindungen zu nicht-4er-Knoten, also der Bedingung nach Blätter. Insgesamt folgt also:
4k - (k-1) [mm] \ge [/mm] 2k +2
3k + 1 [mm] \ge [/mm] 2k + 2
k [mm] \ge [/mm] 1
Das ist nach Bedingung der Aufgabenstellung immer erfüllt.
Induktionsschritt
Für k+1 gilt demnach
k+1 [mm] \ge [/mm] 1
Das trifft immer zu. Tatsächlich ist k mind. 1 also k > 0
Ist das korrekt, bzw. vor allem ist die Induktion mathematisch richtig ausgeführt/dargelegt? Bisschen viel gebrabbel.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo,
> Beweise: Wenn ein Baum genau [mm]k\ge1[/mm] Knoten vom Grad 4
> enthält,
> dann besitzt der Baum mindestens 2k + 2 Blätter.
> Das ganze über Induktion nach k.
>
> Induktionsverankerung
> Der Baum hat genau 1 Knoten k mit deg(k) > 1, bzw.
> deg(k)=4
Die Bedeutung von k ist in der Aufgabenstellung bereits festgelegt. Den Knoten jetzt nochmal genauso zu nennen ist extrem verwirrend und absolut kontraproduktiv.
Die Induktionsverankerung ist zusätzlich dazu noch falsch:
Der Baum hat genau einen Knoten e mit deg(e)=4.
> Entsprechend hat der dieser Knoten genau 4 Knoten x mit
> deg(x)=1, also 4 Blätter.
> Also Bedingung erfüllt: 2*1+2 = deg(k)
Auch das ist falsch:
. .
| |
.- . - .
| |
. .
ist ein Baum mit einem Knoten vom Grad 4 mit 5 Blättern.
e hat 4 Knoten. Diese Sind Blätter oder sind mit weiteren Knoten verbunden, die schließlich mindestens ein Blatt haben.
Daher hat der Baum mindestens 4 Blätter.
> Induktionsannahme
> x Knoten k mit deg(k) = 4 und 0 Knoten j mit 1 < deg(j) <
> 4.
Nein. (Du gibst etwas-j- das nicht existiert einen Namen und x ist nicht näher bestimmt )
Die Ind. annahme ist: Hat ein Baum k Knoten [mm] $e_1,\ldots e_k$ [/mm] mit [mm] $deg(e_i)=4$so [/mm] hat er mindestens 2k+2 Blätter.
(wie viele Knoten von anderen Graden er hat ist vollkommen egal)
> Wenn zweite Bedingung nicht erfüllt, also bspw. 1 deg(j)
> = 2, so ändert sich nichts an der Anzahl Blätter. Da es
Es Beispiel beweist nichts, es kann nur widerlegen.
Was ist denn bei deg(j)=5,17,888,68989 usw.?
> sich um einen Baum handelt, geht von einem 4er Grad eine
> Verbindung zum 2er, der 2er hat dann 1 Blatt, wodurch die
> Anzahl der Blätter in Relation zu 4er Grad konstant ist.
> Im Fall 1 deg(j) = 3 entsteht sogar ein Blatt mehr, dies
> ist aber nicht relevant, da 2 *k + 2 die minimale Grenze
> ist.
>
> Damit Kreisfreiheit und Zusammenhang für den Baum erfüllt
> ist, gibt es zwischen den 4er Knoten immer 1 Verbindung.
> Entsprechend (k-1) Verbindungen zu nicht-Blätter.
Nein. Ein 4-Knoten kann ja auch 3 oder 4 Blätter haben (siehe dein Bsp. im Ind.anfang)
> Die
> Knoten k, für die das zu trifft, haben deg(k) = 4,
> dementsprechend gibt es
> 4k - (k-1) Verbindungen zu nicht-4er-Knoten, also der
> Bedingung nach Blätter. Insgesamt folgt also:
>
> 4k - (k-1) [mm]\ge[/mm] 2k +2
> 3k + 1 [mm]\ge[/mm] 2k + 2
> k [mm]\ge[/mm] 1
>
> Das ist nach Bedingung der Aufgabenstellung immer
> erfüllt.
Ja und was genau soll das jetzt zeigen?
> Induktionsschritt
> Für k+1 gilt demnach
> k+1 [mm]\ge[/mm] 1
> Das trifft immer zu. Tatsächlich ist k mind. 1 also k >
> 0
Nein, das hat mit dem Induktionschritt gar nichts zu tun.
Der Induktionsschritt ist der Beweis, dass aus der Ind. annahme die Ind. behauptung folgt, also das was du drüber versucht hast.
> Ist das korrekt, bzw. vor allem ist die Induktion
> mathematisch richtig ausgeführt/dargelegt? Bisschen viel
> gebrabbel.
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:20 Fr 25.07.2014 | | Autor: | Morgyr |
Vielen Dank schon mal soweit, neuer Versuch. Und diesmal wirklich über eine Induktion nach k.
Die Menge aller Knoten mit Grad 4 ist [mm] \{e_{1},\ldots,e_{i}\}, [/mm] die Größe dieser Menge lautet k und beträgt mindestens 1.
Da ein Baum zusammenhängend ist, gibt es genau (k-1) Verbindungen zur Verknüpfung von [mm] e_{i}. [/mm] Wenn es 0 dieser Verbindungen geben würde, gäbe es insgesamt mindestens 4k Verbindungen. Die (4k - (k-1)) übrigen Verbindungen bilden die minimale Menge der Blätter und der Knoten, die selber wiederum mindestens 1 Blatt haben.
Der Baum hat somit mindestens 4k - (k-1) Blätter.
Induktionsverankerung:
Der Baum hat genau k=1 Knoten e mit deg(e)=4.
e hat also genau 4 Knoten, die entweder Blätter sind oder Knoten, die jeweils selbst mindestens 1 Blatt haben müssen.
Der Baum hat also mindestens 4 Blätter.
2*1 + 2 = 4 und 4*1 - (1-1) = 4
Für k=1 hat der Baum mindestens 2k+2 Blätter.
Induktionsannahme: Hat ein Baum k Knoten $ [mm] e_1,\ldots e_k [/mm] $ mit [mm] deg(e_{i}), [/mm] so hat er mindestens 2k+2 Blätter.
Die Annahme lautet 4k - (k-1) [mm] \ge [/mm] 2k + 2.
Daraus folgt die Behauptung:
4(k+1) - (k+1-1) [mm] \ge [/mm] 2(k + 1) + 2
4k + 4 - k [mm] \ge [/mm] 2k + 2 + 2
4k - (k-1) + 3 [mm] \ge [/mm] 2k + 2 + 2
Auf Grund der Annahme und 3 > 2 ist die Ungleichung erfüllt und die Behauptung bewiesen.
Da der Baum für k=1 mindestens 2k+2 Blätter hat, trifft dies für alle k [mm] \ge [/mm] 1 zu.
Ist dieses 4k-(k-1) zeugs überhaupt legitim? Könnte ich glatt noch ne Induktion für raushauen.
|
|
|
| |
|
> Vielen Dank schon mal soweit, neuer Versuch. Und diesmal
> wirklich über eine Induktion nach k.
>
>
> Die Menge aller Knoten mit Grad 4 ist
> [mm]\{e_{1},\ldots,e_{i}\},[/mm] die Größe dieser Menge lautet k
> und beträgt mindestens 1.
Das ist unnötig kompliziert geschrieben, du verwendest eine zusätzliche Benennung i, die nicht nötig ist:
Die Menge aller Knoten mit Grad 4 ist
> [mm]\{e_{1},\ldots,e_{k}\},[/mm] mit [mm] $k\geq [/mm] 1$
> Da ein Baum zusammenhängend ist, gibt es genau (k-1)
> Verbindungen zur Verknüpfung von [mm]e_{i}.[/mm]
Was ist doe Verknüpfung von [mm] $e_i$? [/mm] Und wieso ausgerechnet dieser spezielle Knoten, der letzte in der Aufzählung?
> Wenn es 0 dieser
> Verbindungen geben würde, gäbe es insgesamt mindestens 4k
> Verbindungen. Die (4k - (k-1)) übrigen Verbindungen bilden
> die minimale Menge der Blätter und der Knoten, die selber
> wiederum mindestens 1 Blatt haben.
> Der Baum hat somit mindestens 4k - (k-1) Blätter.
Nein.
. .
| |
.- . - .- .
| |
. .
hat keine 4*2-(2-1)=7 Blätter.
> Induktionsverankerung:
> Der Baum hat genau k=1 Knoten e mit deg(e)=4.
> e hat also genau 4 Knoten, die entweder Blätter sind oder
> Knoten, die jeweils selbst mindestens 1 Blatt haben
> müssen.
> Der Baum hat also mindestens 4 Blätter.
> 2*1 + 2 = 4 und 4*1 - (1-1) = 4
> Für k=1 hat der Baum mindestens 2k+2 Blätter.
>
> Induktionsannahme: Hat ein Baum k Knoten [mm]e_1,\ldots e_k[/mm] mit
> [mm]deg(e_{i}),[/mm] so hat er mindestens 2k+2 Blätter.
> Die Annahme lautet 4k - (k-1) [mm]\ge[/mm] 2k + 2.
Die Annahme steht in der Zeile darüber. Wo kommt diese Annahme her?
> Daraus folgt die Behauptung:
Und was ist die Behauptung?
> 4(k+1) - (k+1-1) [mm]\ge[/mm] 2(k + 1) + 2
> 4k + 4 - k [mm]\ge[/mm] 2k + 2 + 2
> 4k - (k-1) + 3 [mm]\ge[/mm] 2k + 2 + 2
> Auf Grund der Annahme und 3 > 2 ist die Ungleichung
> erfüllt und die Behauptung bewiesen.
> Da der Baum für k=1 mindestens 2k+2 Blätter hat, trifft
> dies für alle k [mm]\ge[/mm] 1 zu.
>
>
> Ist dieses 4k-(k-1) zeugs überhaupt legitim? Könnte ich
> glatt noch ne Induktion für raushauen.
Ich weiß nicht mal was mit 4k-(k-1) Zeugs überhaupt gemeint ist.
Formulier doch bitte erstmal was überhaupt die Ind.bahauptung ist, das scheint nicht klar zu sein.
Außerdem wär es wohl ganz hilfreich sich mal ein paar Beispielbäume anzuschauen um zu sehen was in den Fällen passiert.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:22 Sa 26.07.2014 | | Autor: | Morgyr |
Annahme: Hat ein Baum k Knoten $ [mm] \{e_{1},\ldots,e_{k}\}, [/mm] $ mit [mm] deg(e_{i})=4 [/mm] so hat er mindestens 2k+2 Blätter.
Behauptung: Hat ein Baum k+1 Knoten $ [mm] \{e_{1},\ldots,e_{k},e_{k+1}\}, [/mm] $ mit [mm] deg(e_{i})=4,
[/mm]
so hat er mindestens 2(k+1)+2=2k+2+2 Blätter.
Vielleicht mal doch noch ne sinnvolle Idee.
Für jeden weiteren Knoten mit Grad 4 wird die minimale Anzahl Blätter über die Formel 2k+2 um genau 2 größer. Um diesen Knoten an den Baum zu hängen, wird eine Verbindung von ihm selbst und eine vom Baum benötigt. Dazu wird 1 Blatt entfernt, und der neue Knoten angehangen, der dann genau 3 Blätter hat. In der Summe also 2 neue Blätter.
|
|
|
| |
|
> Annahme: Hat ein Baum k Knoten [mm]\{e_{1},\ldots,e_{k}\},[/mm] mit
> [mm]deg(e_{i})=4[/mm] so hat er mindestens 2k+2 Blätter.
>
> Behauptung: Hat ein Baum k+1 Knoten
> [mm]\{e_{1},\ldots,e_{k},e_{k+1}\},[/mm] mit [mm]deg(e_{i})=4,[/mm]
> so hat er mindestens 2(k+1)+2=2k+2+2 Blätter.
richtig.
> Vielleicht mal doch noch ne sinnvolle Idee.
> Für jeden weiteren Knoten mit Grad 4 wird die minimale
> Anzahl Blätter über die Formel 2k+2 um genau 2 größer.
> Um diesen Knoten an den Baum zu hängen, wird eine
> Verbindung von ihm selbst und eine vom Baum benötigt. Dazu
> wird 1 Blatt entfernt, und der neue Knoten angehangen, der
> dann genau 3 Blätter hat. In der Summe also 2 neue
> Blätter.
Die Idee ist sehr sinnvoll.
Allerdings passt es so wie es aufgeschrieben ist nicht, du beweist in die falsche Richtung.
Es ist die Ind.beh. zu zeigen, das heißt du betrachtest einen Baum mit k+1 Knoten vom Grad 4, Diesen zerlegst du dann analog zu deiner Methode um die Ind.annahme verwenden zu können.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:05 So 27.07.2014 | | Autor: | Morgyr |
Stimmt auch wieder.
Wird ein Knoten [mm] e_{i} [/mm] entfernt, werden automatisch auch 3 Knoten entfernt, die entweder Blätter oder Knoten sind, die selbst mindestens 1 Blatt haben. Der zu diesem Knoten [mm] e_{i} [/mm] adjazente Knoten erhält dadurch aber einen freien Grad und somit genau ein neues Blatt.
Bei k Knoten mit Grad 4 fehlen gegenüber k+1 Knoten also genau 2 Blätter, die adjazent zu [mm] e_{i} [/mm] waren und die Anzahl beträgt mindestens 2k + 2 + 2 - 2 = 2k + 2
Vielen Dank.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:04 Sa 26.07.2014 | | Autor: | Morgyr |
| Aufgabe | Beweise durch Induktion über d, dass der d-dimensionale Hyperwürfel [mm] Q_{d} [/mm] hamiltonsch ist für d [mm] \ge [/mm] 2
[mm] Q_{d} [/mm] = [mm] (V_{d},E_{d})
[/mm]
[mm] V_{d} [/mm] = [mm] \{0,1\}^d
[/mm]
Die Knoten heißen [mm] x=\{x_{1},\ldots,x_{d}\}\in{0,1}^d
[/mm]
Kanten existieren zwischen zwei Knoten, die sich nur in einer Stelle [mm] x_{i} [/mm] unterscheiden. |
In dem Fall ist mir wenigstens die Herangehensweise klar.
Allerdings verstricke ich mich wieder in einem Mischmasch von Definition, und vor allem bin ich nicht so überzeugt von meinem abschließenden Absatz.
Der Grad der Knoten ist zueinander immer gleich, denn jeder Knoten ist mit jeweils den Knoten verbunden, die sich nur in einer Stelle [mm] x_{i} [/mm] unterscheiden. Der Grad der Knoten ist somit d, da die Größe der Menge x je d ist. Anzahl der Knoten ist durch [mm] \{0,1\}^d [/mm] gegeben, bzw. [mm] 2^d.
[/mm]
Ein Graph ist hamiltonsch wenn der Grad von zwei Knoten, die nicht miteinander verbunden sind, zusammen größer ist als die Anzahl Knoten. Da der Grad aller Knoten gleich ist, ist eine Unterscheidung der Knoten nicht nötig.
Verankerung ist d=2
2*2 [mm] \ge 2^2 [/mm]
4 [mm] \ge [/mm] 4
[mm] Q_{2} [/mm] ist hamiltonsch.
Annahme: Der d-dimensionale Hyperwürfel [mm] Q_{d} [/mm] ist hamiltonsch.
Behauptung: Der (d+1)-dimensionale Hyperwürfel [mm] Q_{d+1} [/mm] ist hamiltonsch.
[mm] Q_{d+1} [/mm] hat 2^(d+1) Knoten mit [mm] x_{i} \in [/mm] x = [mm] (x_{1},\ldots,x_{d},x_{d+1})\in\{0,1\}^{d+1}
[/mm]
[mm] Q_{d+1} [/mm] besteht aus 2 [mm] Q_{d} [/mm] mit zusätzlichen Kanten [mm] |V_{d}|, [/mm] da die Knoten der beiden [mm] Q_{d} [/mm] sich nur in der Stelle [mm] x_{d+1} [/mm] unterscheiden und diese nur 2 Werte annehmen kann.
Somit lässt sich jeder beliebige Hyperwürfel mit Grad [mm] \ge [/mm] 2 in mehrere [mm] Q_{2} [/mm] zerlegen. [mm] Q_{2} [/mm] ist hamiltonsch. Der Hamiltonkreis über 2 [mm] Q_{2} [/mm] erfolgt dann durch Umlegung je einer Kante für den Dimensionswechsel hin und zurück.
[mm] Q_{d+1} [/mm] ist somit hamiltonsch, und daher jeder beliebige Hyperwürfel mit Grad [mm] \ge [/mm] 2.
|
|
|
| |
|
Hallo,
> Beweise durch Induktion über d, dass der d-dimensionale
> Hyperwürfel [mm]Q_{d}[/mm] hamiltonsch ist für d [mm]\ge[/mm] 2
>
> [mm]Q_{d}[/mm] = [mm](V_{d},E_{d})[/mm]
> [mm]V_{d}[/mm] = [mm]\{0,1\}^d[/mm]
> Die Knoten heißen [mm]x=\{x_{1},\ldots,x_{d}\}\in{0,1}^d[/mm]
Das ist Unsinn. Die Knotenmenge hat bereits eine Namen: V. Da brauchts nicht noch einen. Ferner sind es [mm] $2^d$ [/mm] Knoten wie du selber später feststellst, also:
[mm] $V=\{x_1, \ldots , x_{2^d} \}$
[/mm]
> Kanten existieren zwischen zwei Knoten, die sich nur in
> einer Stelle [mm]x_{i}[/mm] unterscheiden.
> In dem Fall ist mir wenigstens die Herangehensweise klar.
> Allerdings verstricke ich mich wieder in einem Mischmasch
> von Definition, und vor allem bin ich nicht so überzeugt
> von meinem abschließenden Absatz.
>
>
> Der Grad der Knoten ist zueinander immer gleich, denn jeder
> Knoten ist mit jeweils den Knoten verbunden, die sich nur
> in einer Stelle [mm]x_{i}[/mm]
Nach deiner eigenen Benennung ist [mm] $x_i$ [/mm] ein Knoten als solche also keine Stelle.
>unterscheiden. Der Grad der Knoten
> ist somit d, da die Größe der Menge x je d ist.
Das würde bedeuten, dass jeder Knoten mit jedem anderen Knoten inklusive sich selbst verbunden ist. Was nicht sein kann.
> Anzahl
> der Knoten ist durch [mm]\{0,1\}^d[/mm] gegeben, bzw. [mm]2^d.[/mm]
Zwei Zeilen vorher schriebst du noch (fälschlicherweise), dass die Anzahl der knoten d ist. Merkst du sowas nicht beim schreiben?
> Ein Graph ist hamiltonsch wenn der Grad von zwei Knoten,
> die nicht miteinander verbunden sind, zusammen größer ist
> als die Anzahl Knoten.
Der Satz wär mir neu. Was heißt in dem Kontext überhaupt unverbunden?
In den Hyperwürfeln gibt es zwischen allen Knoten einen Weg, wie soll die Aussage hier überhaupt angewandt werden?
> Da der Grad aller Knoten gleich ist,
> ist eine Unterscheidung der Knoten nicht nötig.
> Verankerung ist d=2
> 2*2 [mm]\ge 2^2[/mm]
> 4 [mm]\ge[/mm] 4
> [mm]Q_{2}[/mm] ist hamiltonsch.
Naheliegend wäre doch auch hier, wie später im Induktionsschritt, einen Hamiltonkreis zu konstruieren.
> Annahme: Der d-dimensionale Hyperwürfel [mm]Q_{d}[/mm] ist
> hamiltonsch.
> Behauptung: Der (d+1)-dimensionale Hyperwürfel [mm]Q_{d+1}[/mm]
> ist hamiltonsch.
> [mm]Q_{d+1}[/mm] hat 2^(d+1) Knoten mit [mm]x_{i} \in[/mm] x =
> [mm](x_{1},\ldots,x_{d},x_{d+1})\in\{0,1\}^{d+1}[/mm]
> [mm]Q_{d+1}[/mm] besteht aus 2 [mm]Q_{d}[/mm] mit zusätzlichen Kanten
> [mm]|V_{d}|,[/mm] da die Knoten der beiden [mm]Q_{d}[/mm] sich nur in der
> Stelle [mm]x_{d+1}[/mm] unterscheiden und diese nur 2 Werte annehmen
> kann.
> Somit lässt sich jeder beliebige Hyperwürfel mit Grad
> [mm]\ge[/mm] 2 in mehrere [mm]Q_{2}[/mm] zerlegen. [mm]Q_{2}[/mm] ist hamiltonsch. Der
> Hamiltonkreis über 2 [mm]Q_{2}[/mm] erfolgt dann durch Umlegung je
> einer Kante für den Dimensionswechsel hin und zurück.
> [mm]Q_{d+1}[/mm] ist somit hamiltonsch, und daher jeder beliebige
> Hyperwürfel mit Grad [mm]\ge[/mm] 2.
Die Idee ist wohl richtig, aber sehr schwammig formuliert. Führe nicht auf Quadrate zurück sondern auf den Hyperwürfel vom Grad d, du machst hier ja eine Induktion.
P.S. Bitte lege für eine neue Aufgabe auch einen neuen Thread an, sonst kann es unnötig unübersichtlich werden.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:44 Sa 26.07.2014 | | Autor: | Morgyr |
> Hallo,
>
> > Beweise durch Induktion über d, dass der d-dimensionale
> > Hyperwürfel [mm]Q_{d}[/mm] hamiltonsch ist für d [mm]\ge[/mm] 2
> >
> > [mm]Q_{d}[/mm] = [mm](V_{d},E_{d})[/mm]
> > [mm]V_{d}[/mm] = [mm]\{0,1\}^d[/mm]
> > Die Knoten heißen [mm]x=\{x_{1},\ldots,x_{d}\}\in{0,1}^d[/mm]
> Das ist Unsinn. Die Knotenmenge hat bereits eine Namen: V.
> Da brauchts nicht noch einen. Ferner sind es [mm]2^d[/mm] Knoten wie
> du selber später feststellst, also:
> [mm]V=\{x_1, \ldots , x_{2^d} \}[/mm]
Hm, heißen..
Die Knoten sind von der Form [mm]x=\{x_{1},\ldots,x_{d}\}\in\{0,1\}^d[/mm]
..trifft es wohl besser.
> > Kanten existieren
....
> > Ein Graph ist hamiltonsch wenn der Grad von zwei Knoten,
> > die nicht miteinander verbunden sind, zusammen größer ist
> > als die Anzahl Knoten.
> Der Satz wär mir neu. Was heißt in dem Kontext
> überhaupt unverbunden?
> In den Hyperwürfeln gibt es zwischen allen Knoten einen
> Weg, wie soll die Aussage hier überhaupt angewandt
> werden?
Nun, Fachbegriff.
Ein Graph ist hamiltonsch, wenn der Grad von zwei Knoten, die nicht zueinander adjazent sind, zusammen größer ist als die Anzahl Knoten.
> > Da der Grad aller Knoten gleich ist,
> > ist eine Unterscheidung der Knoten nicht nötig.
> > Verankerung ist d=2
> > 2*2 [mm]\ge 2^2[/mm]
> > 4 [mm]\ge[/mm] 4
> > [mm]Q_{2}[/mm] ist hamiltonsch.
> Naheliegend wäre doch auch hier, wie später im
> Induktionsschritt, einen Hamiltonkreis zu konstruieren.
Ist es denn grundsätzlich in Ordnung, für die Verankerung einen anderen Beweis zu wählen, als für den Schritt? Unabhängig davon, dass mit Konstruktion mein Text um 100 Zeilen kleiner wird.
Aber wie sieht die Konstruktion aus?
Der Pfad 00 [mm] \to [/mm] 01 [mm] \to [/mm] 11 [mm] \to [/mm] 10 [mm] \to [/mm] 00 bildet einen Hamiltonkreis. Somit ist [mm] Q_{2} [/mm] hamiltonsch...?
> > Annahme: Der d-dimensionale Hyperwürfel [mm]Q_{d}[/mm] ist
> > hamiltonsch.
> > Behauptung: Der (d+1)-dimensionale Hyperwürfel [mm]Q_{d+1}[/mm]
> > ist hamiltonsch.
> > [mm]Q_{d+1}[/mm] hat 2^(d+1) Knoten mit [mm]x_{i} \in[/mm] x =
> > [mm](x_{1},\ldots,x_{d},x_{d+1})\in\{0,1\}^{d+1}[/mm]
> > [mm]Q_{d+1}[/mm] besteht aus 2 [mm]Q_{d}[/mm] mit zusätzlichen Kanten
> > y=[mm]|V_{d}|,[/mm] da die Knoten der beiden [mm]Q_{d}[/mm] sich nur in der
> > Stelle [mm]x_{d+1}[/mm] unterscheiden und diese nur 2 Werte annehmen
> > kann.
[mm] Q_{d} [/mm] ist per Annahme hamiltonsch, wodurch [mm] Q_{d+1} [/mm] zwei Kreise enthält. Entfernt man aus einem Kreis eine beliebige Kante inzident zu [mm] \{x_{1}, \ldots ,x_{d}, 0\} [/mm] und aus dem zweiten Kreis die entsprechende Kante inzident zu [mm] \{x_{1},\ldots,x_{d}, 1\} [/mm] und verknüpft anschließend die Anfangs- und Endpunkte der beiden entstandenen Pfade mit einer Kante e [mm] \in [/mm] E, entsteht ein Hamiltonkreis.
Da [mm] Q_{d+1} [/mm] aus 2 [mm] Q_{d} [/mm] besteht, folgt, dass [mm] Q_{d} [/mm] für d [mm] \ge [/mm] 3 aus 2 [mm] Q_{d-1} [/mm] besteht. Daher besteht [mm] Q_{d+1} [/mm] aus 2^(d+1-f) [mm] Q_{f} [/mm] für f [mm] \ge [/mm] 2, bzw. [mm] Q_{d} [/mm] aus 2^(d-f) [mm] Q_{f}.
[/mm]
Führt man die Aufteilung für beliebige [mm] Q_{d} [/mm] bis f=2 durch, erhält man also mehrere [mm] Q_{2} [/mm] gerader Anzahl, die hamiltonsch sind. Über die o.g. Verknüpfung sind somit auch alle [mm] Q_{d} [/mm] hamiltonsch.
> P.S. Bitte lege für eine neue Aufgabe auch einen neuen
> Thread an, sonst kann es unnötig unübersichtlich werden.
Alles klar.
|
|
|
| |
|
> > Hallo,
> >
> > > Beweise durch Induktion über d, dass der d-dimensionale
> > > Hyperwürfel [mm]Q_{d}[/mm] hamiltonsch ist für d [mm]\ge[/mm] 2
> > >
> > > [mm]Q_{d}[/mm] = [mm](V_{d},E_{d})[/mm]
> > > [mm]V_{d}[/mm] = [mm]\{0,1\}^d[/mm]
> > > Die Knoten heißen
> [mm]x=\{x_{1},\ldots,x_{d}\}\in{0,1}^d[/mm]
> > Das ist Unsinn. Die Knotenmenge hat bereits eine Namen:
> V.
> > Da brauchts nicht noch einen. Ferner sind es [mm]2^d[/mm] Knoten wie
> > du selber später feststellst, also:
> > [mm]V=\{x_1, \ldots , x_{2^d} \}[/mm]
> Hm, heißen..
> Die Knoten sind von der Form
> [mm]x=\{x_{1},\ldots,x_{d}\}\in\{0,1\}^d[/mm]
> ..trifft es wohl besser.
Nein, tut es nicht. Ich ging davon aus, dass du das meintest (die Klammern sind aus dem Quelltext ersichtlich)
> > > Kanten existieren
> ....
> > > Ein Graph ist hamiltonsch wenn der Grad von zwei
> Knoten,
> > > die nicht miteinander verbunden sind, zusammen größer ist
> > > als die Anzahl Knoten.
> > Der Satz wär mir neu. Was heißt in dem Kontext
> > überhaupt unverbunden?
> > In den Hyperwürfeln gibt es zwischen allen Knoten einen
> > Weg, wie soll die Aussage hier überhaupt angewandt
> > werden?
> Nun, Fachbegriff.
> Ein Graph ist hamiltonsch, wenn der Grad von zwei Knoten,
> die nicht zueinander adjazent sind, zusammen größer ist
> als die Anzahl Knoten.
Nun, Fachbegriffe richtig verwenden. Es heißt adjezent oder verbunden nicht miteinander verbunden. Ferner hast du die Ore-Bedingung insgesamt sehr schwammig formuliert, es z.B. um je zwei Knoten, Dein text ist so formuliert, dass es genügt zwei solche Knoten zu haben, was falsch ist. Ferner ist größer (>) hier falsch, es ist größer oder gleich. Und zusätzlich als Hinweis: Die Bedingung ist hinreichend, aber nicht notwendig.
> > > Da der Grad aller Knoten gleich ist,
> > > ist eine Unterscheidung der Knoten nicht nötig.
> > > Verankerung ist d=2
> > > 2*2 [mm]\ge 2^2[/mm]
> > > 4 [mm]\ge[/mm] 4
> > > [mm]Q_{2}[/mm] ist hamiltonsch.
> > Naheliegend wäre doch auch hier, wie später im
> > Induktionsschritt, einen Hamiltonkreis zu konstruieren.
> Ist es denn grundsätzlich in Ordnung, für die Verankerung
> einen anderen Beweis zu wählen, als für den Schritt?
Natürlich. Aber es ist sinnvoll nicht mit Kanonen (wie der Ore-Bedingung) auf Spatzen zu schießen.
> Unabhängig davon, dass mit Konstruktion mein Text um 100
> Zeilen kleiner wird.
Allein das wär's schon wert. Zusätzlich fördert es das u.a. Verständnis mehr.
> Aber wie sieht die Konstruktion aus?
> Der Pfad 00 [mm]\to[/mm] 01 [mm]\to[/mm] 11 [mm]\to[/mm] 10 [mm]\to[/mm] 00 bildet einen
> Hamiltonkreis. Somit ist [mm]Q_{2}[/mm] hamiltonsch...?
Ja.
> > > Annahme: Der d-dimensionale Hyperwürfel [mm]Q_{d}[/mm] ist
> > > hamiltonsch.
> > > Behauptung: Der (d+1)-dimensionale Hyperwürfel
> [mm]Q_{d+1}[/mm]
> > > ist hamiltonsch.
> > > [mm]Q_{d+1}[/mm] hat 2^(d+1) Knoten mit [mm]x_{i} \in[/mm] x =
> > > [mm](x_{1},\ldots,x_{d},x_{d+1})\in\{0,1\}^{d+1}[/mm]
Siehe oben, das sind viel zu wenig Knoten.
> > > [mm]Q_{d+1}[/mm] besteht aus 2 [mm]Q_{d}[/mm] mit zusätzlichen Kanten
> > > y=[mm]|V_{d}|,[/mm] da die Knoten der beiden [mm]Q_{d}[/mm] sich nur in der
> > > Stelle [mm]x_{d+1}[/mm] unterscheiden und diese nur 2 Werte annehmen
> > > kann.
> [mm]Q_{d}[/mm] ist per Annahme hamiltonsch, wodurch [mm]Q_{d+1}[/mm] zwei
> Kreise enthält. Entfernt man aus einem Kreis eine
> beliebige Kante inzident zu [mm]\{x_{1}, \ldots ,x_{d}, 0\}[/mm]
0 ist kein Knoten, hat also in einer Menge mit Knoten nichts verloren.
> und
> aus dem zweiten Kreis die entsprechende Kante inzident zu
> [mm]\{x_{1},\ldots,x_{d}, 1\}[/mm]
Auch hier ist 1 kein Knoten.
> und verknüpft anschließend die
> Anfangs- und Endpunkte der beiden entstandenen Pfade mit
> einer Kante e [mm]\in[/mm] E, entsteht ein Hamiltonkreis.
Das stimmt zwar, aber nicht mit deiner Notation, die sagt nämlich was ganz anderes.
Laut deiner Notation liegen die Knoten [mm] $x_1,\ldots [/mm] , [mm] x_d$ [/mm] in beiden(!) Hamiltonkreisen. Dein neuer Hamiltonkreis enthält damit [mm] 4x_1, \ldotsx_d,0,1$ [/mm] aber nicht [mm] $x_{d+1}$. [/mm] Der Murks ist alles eine Folge deiner falsch notierten Knotenmenge.
> Da [mm]Q_{d+1}[/mm] aus 2 [mm]Q_{d}[/mm] besteht, folgt, dass [mm]Q_{d}[/mm] für d
> [mm]\ge[/mm] 3 aus 2 [mm]Q_{d-1}[/mm] besteht. Daher besteht [mm]Q_{d+1}[/mm] aus
> 2^(d+1-f) [mm]Q_{f}[/mm] für f [mm]\ge[/mm] 2, bzw. [mm]Q_{d}[/mm] aus 2^(d-f)
> [mm]Q_{f}.[/mm]
> Führt man die Aufteilung für beliebige [mm]Q_{d}[/mm] bis f=2
> durch, erhält man also mehrere [mm]Q_{2}[/mm] gerader Anzahl, die
> hamiltonsch sind. Über die o.g. Verknüpfung sind somit
> auch alle [mm]Q_{d}[/mm] hamiltonsch.
Die Rückführung auf den Fall d=2 ist vollkommen unnötig. Dafür machst du hier doch die Induktion.
> > P.S. Bitte lege für eine neue Aufgabe auch einen neuen
> > Thread an, sonst kann es unnötig unübersichtlich werden.
> Alles klar.
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:01 So 27.07.2014 | | Autor: | Morgyr |
> > Hm, heißen..
> > Die Knoten sind von der Form
> > [mm]x=\{x_{1},\ldots,x_{d}\}\in\{0,1\}^d[/mm]
> > ..trifft es wohl besser.
> Nein, tut es nicht. Ich ging davon aus, dass du das
> meintest (die Klammern sind aus dem Quelltext ersichtlich)
Ja, die Klammern sind nur hinzugekommen, weil ich gesehen hatte, dass der Slash fehlte.
Nun gut, dann würde ich um einen Vorschlag bitten, wie Du es ausdrücken würdest. Dieses "von der Form" entspricht einer Angabe aus der Aufgabenstellung, die als Definition dient.
"Der d-dimensionale Hyperwürfel [mm] Q_{d} [/mm] ist ein Graph mit Knoten der
Form x = [mm] (x_{1},\ldots,x_{d}) \in \{0,1\}^2 [/mm] und [...]"
Als Informatiker würde ich hier jetzt n Aufsatz über Binärcodierung schreiben.
> > > > Kanten existieren
> > ....
> > schlechte Definition von Ore-Bedingung
> Nun, Fachbegriffe richtig verwenden. Es heißt adjezent
> oder verbunden nicht miteinander verbunden. Ferner hast du
> die Ore-Bedingung insgesamt sehr schwammig formuliert, es
> z.B. um je zwei Knoten, Dein text ist so formuliert, dass
> es genügt zwei solche Knoten zu haben, was falsch ist.
> Ferner ist größer (>) hier falsch, es ist größer oder
> gleich. Und zusätzlich als Hinweis: Die Bedingung ist
> hinreichend, aber nicht notwendig.
adjezent ist aber ein Flüchtigkeitsfehler?
Ja, gut. Richtig wäre es, einfach die Definition aus dem Buch abzuschreiben. Der Versuch, sich das für das Forum zu sparen und stattdessen n blöden Satz da hinzuknallen, funktioniert also nicht für mich, weil ich noch nie in der Lage war, irgendwas so auszudrücken, wie ich es meine. Die Definition schreib ich jetzt trotzdem nicht ab.
Aber die hinreichende Bedingung ist erfüllt. Ich habe das eigentlich immer so verstanden, dass wenn die hinreichende Bedingung erfüllt ist, der Graph hamiltonsch ist, aber nur weil ein Graph hamiltonsch ist, heißt es nicht, dass die hinreichende Bedingung erfüllt sein muss.
Insofern sollte das doch für eine Verankerung hinreichend sein?
> >
.......
> > Da [mm]Q_{d+1}[/mm] aus 2 [mm]Q_{d}[/mm] besteht, folgt, dass [mm]Q_{d}[/mm] für
> d
> > [mm]\ge[/mm] 3 aus 2 [mm]Q_{d-1}[/mm] besteht. Daher besteht [mm]Q_{d+1}[/mm] aus
> > 2^(d+1-f) [mm]Q_{f}[/mm] für f [mm]\ge[/mm] 2, bzw. [mm]Q_{d}[/mm] aus 2^(d-f)
> > [mm]Q_{f}.[/mm]
> > Führt man die Aufteilung für beliebige [mm]Q_{d}[/mm] bis f=2
> > durch, erhält man also mehrere [mm]Q_{2}[/mm] gerader Anzahl, die
> > hamiltonsch sind. Über die o.g. Verknüpfung sind somit
> > auch alle [mm]Q_{d}[/mm] hamiltonsch.
> Die Rückführung auf den Fall d=2 ist vollkommen
> unnötig. Dafür machst du hier doch die Induktion.
Ahja, ich versuch glaub ich immer das Rad neu zu erfinden, und die Induktion zusätzlich auch noch zu beweisen. Aber die Induktion ist ja schon bewiesen. So ein Glück :D
> > > P.S. Bitte lege für eine neue Aufgabe auch einen
> neuen
> > > Thread an, sonst kann es unnötig unübersichtlich werden.
> > Alles klar.
> >
>
|
|
|
| |
|
> > > Hm, heißen..
> > > Die Knoten sind von der Form
> > > [mm]x=\{x_{1},\ldots,x_{d}\}\in\{0,1\}^d[/mm]
> > > ..trifft es wohl besser.
> > Nein, tut es nicht. Ich ging davon aus, dass du das
> > meintest (die Klammern sind aus dem Quelltext ersichtlich)
> Ja, die Klammern sind nur hinzugekommen, weil ich gesehen
> hatte, dass der Slash fehlte.
> Nun gut, dann würde ich um einen Vorschlag bitten, wie Du
> es ausdrücken würdest.
Diesen Vorschlag hab ich in der ersten Antwort bereits gemacht.
> Dieses "von der Form" entspricht
> einer Angabe aus der Aufgabenstellung, die als Definition
> dient.
> "Der d-dimensionale Hyperwürfel [mm]Q_{d}[/mm] ist ein Graph mit
> Knoten der
> Form x = [mm](x_{1},\ldots,x_{d}) \in \{0,1\}^2[/mm] und [...]"
> Als Informatiker würde ich hier jetzt n Aufsatz über
> Binärcodierung schreiben.
> > > > > Kanten existieren
> > > ....
> > > schlechte Definition von Ore-Bedingung
> > Nun, Fachbegriffe richtig verwenden. Es heißt adjezent
> > oder verbunden nicht miteinander verbunden. Ferner hast du
> > die Ore-Bedingung insgesamt sehr schwammig formuliert, es
> > z.B. um je zwei Knoten, Dein text ist so formuliert, dass
> > es genügt zwei solche Knoten zu haben, was falsch ist.
> > Ferner ist größer (>) hier falsch, es ist größer oder
> > gleich. Und zusätzlich als Hinweis: Die Bedingung ist
> > hinreichend, aber nicht notwendig.
> adjezent ist aber ein Flüchtigkeitsfehler?
Tippfehler, ja.
> Ja, gut. Richtig wäre es, einfach die Definition aus dem
> Buch abzuschreiben. Der Versuch, sich das für das Forum zu
> sparen und stattdessen n blöden Satz da hinzuknallen,
> funktioniert also nicht für mich, weil ich noch nie in der
> Lage war, irgendwas so auszudrücken, wie ich es meine.
Dann solltest du dran arbeiten dich richtig auszudrücken. Ist auch und insb. für Informatiker wichtig.
> Die
> Definition schreib ich jetzt trotzdem nicht ab.
> Aber die hinreichende Bedingung ist erfüllt. Ich habe das
> eigentlich immer so verstanden, dass wenn die hinreichende
> Bedingung erfüllt ist, der Graph hamiltonsch ist, aber nur
> weil ein Graph hamiltonsch ist, heißt es nicht, dass die
> hinreichende Bedingung erfüllt sein muss.
> Insofern sollte das doch für eine Verankerung hinreichend
> sein?
Ist es auch.
> > >
> .......
> > > Da [mm]Q_{d+1}[/mm] aus 2 [mm]Q_{d}[/mm] besteht, folgt, dass [mm]Q_{d}[/mm]
> für
> > d
> > > [mm]\ge[/mm] 3 aus 2 [mm]Q_{d-1}[/mm] besteht. Daher besteht [mm]Q_{d+1}[/mm] aus
> > > 2^(d+1-f) [mm]Q_{f}[/mm] für f [mm]\ge[/mm] 2, bzw. [mm]Q_{d}[/mm] aus 2^(d-f)
> > > [mm]Q_{f}.[/mm]
> > > Führt man die Aufteilung für beliebige [mm]Q_{d}[/mm] bis
> f=2
> > > durch, erhält man also mehrere [mm]Q_{2}[/mm] gerader Anzahl, die
> > > hamiltonsch sind. Über die o.g. Verknüpfung sind somit
> > > auch alle [mm]Q_{d}[/mm] hamiltonsch.
> > Die Rückführung auf den Fall d=2 ist vollkommen
> > unnötig. Dafür machst du hier doch die Induktion.
> Ahja, ich versuch glaub ich immer das Rad neu zu erfinden,
> und die Induktion zusätzlich auch noch zu beweisen. Aber
> die Induktion ist ja schon bewiesen. So ein Glück :D
> > > > P.S. Bitte lege für eine neue Aufgabe auch einen
> > neuen
> > > > Thread an, sonst kann es unnötig unübersichtlich werden.
> > > Alles klar.
> > >
> >
>
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 20:37 So 27.07.2014 | | Autor: | Morgyr |
> Diesen Vorschlag hab ich in der ersten Antwort bereits gemacht.
Da ging es aber...ähm..um die mathematische Bezeichnung der Knoten. Ich will ja irgendwie die Namensgebung umschreiben, um später über die Stellen zur argumentieren. Da hilft mir keine abstrakte Bezeichnung [mm] x_{1} [/mm] für den Knoten 000000.
Aber lassen wir das mal mit den Stellen weg, letzter Versuch:
Entfernt man aus einem Kreis eine beliebige Kante und aus dem zweiten Kreis eine Kante, die sich nur in einer Dimension zur vorigen Kante unterscheidet, und verknüpft [...]
Ist die Argumentation legitim?
> Dann solltest du dran arbeiten dich richtig auszudrücken. Ist auch und insb. für Informatiker wichtig.
Sicher, gebe ich dir voll und ganz recht, aber bis dafür sind noch eine Menge Beweise nötig..vielleicht habe ich dazu ab Oktober noch mehr Gelegenheit.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:20 Di 29.07.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
