Planare Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:18 Do 03.01.2008 | | Autor: | Kar_o |
| Aufgabe | Der Graph [mm] Q_n=(V,E) [/mm] mit [mm] V={0,1}^n [/mm] , in dem genau dann $ {u,v} [mm] \in [/mm] E $ gilt, wenn sich die Wörter [mm] u=u_1 u_2 ...u_n [/mm] und [mm] v=v_1 v_2 ...v_n [/mm] an genau einer Position $ i [mm] \in [/mm] {1,...,n} $ unterscheiden, wird n-dimensionaler Würfel genannt.
a) Wieviele Ecken und Kanten hat der [mm] Q_n [/mm] ?
b) Für welche n [mm] \in \IN [/mm]
i) ist [mm] Q_n [/mm] bipartit?
ii) existiert ein Eulerkreis in [mm] Q_n
[/mm]
iii) existiert ein Hamiltonkreis in [mm] Q_n
[/mm]
iv) ist [mm] Q_n [/mm] planar? |
Eigentlich hätte ich vorerst keine Frage zu der Aufgabe selbst.
Sondern ich bräuchte erstnochmal eine einfache Erklärung des n-dimensionalen Würfels!
[mm] V={0,1}^n [/mm] --> stellt die Dimenson dar oder? wenn n=2 dann ist es doch 2-dimensonal und ist n=3 ist es 3-dimensonal, oder?
aber was bedeutet das: >> wenn sich die Wörter [mm] u=u_1 u_2 ...u_n [/mm] und [mm] v=v_1 v_2 ...v_n [/mm] an genau einer Position i [mm] \in [/mm] {1,...,n} unterscheiden << ich denke das ist mir nicht klar.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:15 Do 03.01.2008 | | Autor: | koepper |
Hallo,
> Der Graph [mm]Q_n=(V,E)[/mm] mit [mm]V={0,1}^n[/mm] , in dem genau dann [mm]{u,v} \in E[/mm]
> gilt, wenn sich die Wörter [mm]u=u_1 u_2 ...u_n[/mm] und [mm]v=v_1 v_2 ...v_n[/mm]
> an genau einer Position [mm]i \in {1,...,n}[/mm] unterscheiden, wird
> n-dimensionaler Würfel genannt.
>
> a) Wieviele Ecken und Kanten hat der [mm]Q_n[/mm] ?
> b) Für welche n [mm]\in \IN[/mm]
> i) ist [mm]Q_n[/mm] bipartit?
> ii) existiert ein Eulerkreis in [mm]Q_n[/mm]
> iii) existiert ein Hamiltonkreis in [mm]Q_n[/mm]
> iv) ist [mm]Q_n[/mm] planar?
> Eigentlich hätte ich vorerst keine Frage zu der Aufgabe
> selbst.
> Sondern ich bräuchte erstnochmal eine einfache Erklärung
> des n-dimensionalen Würfels!
>
> [mm]V={0,1}^n[/mm] --> stellt die Dimenson dar oder? wenn n=2 dann
> ist es doch 2-dimensonal und ist n=3 ist es 3-dimensonal,
> oder?
so steht es ja in der Aufgabe.
> aber was bedeutet das: >> wenn sich die Wörter [mm]u=u_1 u_2 ...u_n[/mm]
> und [mm]v=v_1 v_2 ...v_n[/mm] an genau einer Position i [mm]\in[/mm]
> {1,...,n} unterscheiden << ich denke das ist mir nicht
> klar.
Die Knoten dieses Graphen sind Wörter über dem Alphabet {0, 1}, d.h. jeder Knoten ist eine Aneinanderreihung von 0en und 1en. Zwei Knoten sind genau dann durch eine Kante verbunden, wenn sich die zugehörigen Wörter an genau einer Stelle unterscheiden.
Am besten du machst dir Beispiele: Wähle n=2 und zeichne den Graphen auf. Dann tue dasselbe mit n=3. Das wird noch einigermaßen übersichtlich. Ab n=4 wird es zu abstrakt.
Übrigens: Wenn du die Wörter (die Knoten repräsentieren) als Koordinaten von Punkten interpretierst und sie auch so einzeichnest, verstehst du warum man den Graphen "Würfel" nennt.
LG
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:23 Sa 05.01.2008 | | Autor: | Kar_o |
| Aufgabe | | Alle Lösungen zu obiger Aufgabe sind zu beweisen bzw. zu begründen. |
Aber genau da liegt jetzt das Problem!
Also ich habe mir um die Aufgabe zu lösen einfach mal [mm] Q_1 [/mm] bis [mm] Q_4 [/mm] aufgemalt und bin alles durch gegangen. Dabei ist mir zunächst aufgefallen, dass:
1a) $n=1\ [mm] \Rightarrow [/mm] V=2 , E=1 \ und \ [mm] \forall_{a\in V} [/mm] \ deg(a)=1=n$
$n=2\ [mm] \Rightarrow [/mm] V=4 , E=4 \ und \ [mm] \forall_{a\in V} [/mm] \ deg(a)=2=n$
$n=3\ [mm] \Rightarrow [/mm] V=8 , E=12 \ und \ [mm] \forall_{a\in V} [/mm] \ deg(a)=3=n$
$n=4\ [mm] \Rightarrow [/mm] V=16 , E=32 \ und \ [mm] \forall_{a\in V} [/mm] \ deg(a)=4=n$
Ecken V: [mm] V=2^n [/mm] und [mm] $\forall_{a\in V} [/mm] \ deg(a)=n $
und daraus folgt dann mittels
$ [mm] \summe_{a \in V} [/mm] \ deg(a)=2|E|$
[mm] \Rightarrow 2^n*n=2|E|
[/mm]
Kanten E: [mm] |E|=2^{n-1}*n
[/mm]
Aber reicht das denn als Beweis, bzw. als Begründung?
Oder wie kann man sonst noch herangehen?
1b)
und auch hier habe ch mir nur wieder durch zeichnen der ersten vier auf alle anderen geschlossen:
i) bei:
n=1 sieht man sofort, dass [mm] Q_1 [/mm] bipartit ist
[mm] Q_2 [/mm] , [mm] Q_3 [/mm] und [mm] Q_4 [/mm] musste ich etwas umzeichenen aber es geht auch,
daraus habe ich geschlussfolgert das es bei allen anderen auch geht
da ja bei einem Würfel immer wegen [mm] 2^n [/mm] immer eine gerade Anzahl an
Ecken herauskommt und nie alle Ecken miteinander in Verbindung
stehen.
Somit müsste [mm] Q_n [/mm] auch bipartit sein.
Aber ich bin mir sicher , dass auch hier noch große Lücken in meinen
Überlegungen sind!
ii) Hier bin ich von folgender Definition ausgeganngen:
Ein zusammenhängender Graph besitzt genau dann einen Eulerzug,
wenn alle Knoten geraden Grad haben.
Da $ [mm] \forall_{a\in V} [/mm] \ deg(a)=n$ und n immer der Dimension entspricht
folgt für mich:
dass für alle [mm] Q_n [/mm] mit n=ungerade: [mm] Q_n [/mm] keinen Eulerkreis besitz
und für alle [mm] Q_n [/mm] mit n=gerade: [mm] Q_n [/mm] einen Eulerkreis besitz.
iii) Auch hier wieder durch reines einzeichnen in n=1 bis n=4 auf alle
geschlussfolgert:
für n>1 existiert ein Hamiltonkreis.
iv) und hier hakt es nun gewaltig. Ich habswieder mit zeichen versucht
und bis n=3 geht es super nur bei 4 gibt es kleine Lösung naja und da
alle weiteren drauf aufbauen nehme ich wieder an das es auch nicht
geht.
Beispiele für Hamiltonkreis und Eulerkreis kann ich ja angeben
Aber ich brauch doch einen ordenlichen Beweis und kann nicht einfach sagen: "So guckt euch die Zeichnung an, da sieht man doch, dass es klar ist."
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:30 Sa 05.01.2008 | | Autor: | koepper |
Hallo,
> 1a) [mm]n=1\ \Rightarrow V=2 , E=1 \ und \ \forall_{a\in V} \ deg(a)=1=n[/mm]
>
> [mm]n=2\ \Rightarrow V=4 , E=4 \ und \ \forall_{a\in V} \ deg(a)=2=n[/mm]
>
> [mm]n=3\ \Rightarrow V=8 , E=12 \ und \ \forall_{a\in V} \ deg(a)=3=n[/mm]
>
> [mm]n=4\ \Rightarrow V=16 , E=32 \ und \ \forall_{a\in V} \ deg(a)=4=n[/mm]
Das sind nur Beipiele, als Beweis reichen die natürlich nicht.
Überlege: Alle Ecken im n-dim. Würfel sind n stellige "Binärzahlen". Wie viele gibt es davon? (Kombinatorik!)
Kanten liegen von einer Ecke zu jeder anderen, die sich in ihrer "Binärdarstellung" nur an einer Stelle unterscheidet.
Wie viele gibts davon?
Wenn du das hast, dann sind deine folgenden Ausführungen ausgezeichnet...
> Ecken V: [mm]V=2^n[/mm] und [mm]\forall_{a\in V} \ deg(a)=n[/mm]
>
> und daraus folgt dann mittels
> [mm]\summe_{a \in V} \ deg(a)=2|E|[/mm]
> [mm]\Rightarrow 2^n*n=2|E|[/mm]
>
> Kanten E: [mm]|E|=2^{n-1}*n[/mm]
>
> Aber reicht das denn als Beweis, bzw. als Begründung?
Das würde dann reichen.
> 1b)
> und auch hier habe ch mir nur wieder durch zeichnen der
> ersten vier auf alle anderen geschlossen:
>
> i) bei:
> n=1 sieht man sofort, dass [mm]Q_1[/mm] bipartit ist
> [mm]Q_2[/mm] , [mm]Q_3[/mm] und [mm]Q_4[/mm] musste ich etwas umzeichenen aber
> es geht auch,
> daraus habe ich geschlussfolgert das es bei allen anderen
> auch geht
Versuche mal, deine Wege durch den Würfel weniger graphisch zu sehen.
Stattdessen versuche, sie mal durch "Umschalten von Binärstellen" in der Knotendarstellung zu machen.
Du weißt ja, daß je 2 Knoten verbunden sind, wenn sie sich in genau einer Stelle unterscheiden... OK?
Und dann überlege einfach: Ein Graph ist genau dann bipartit, wenn er keinen Kreis ungerader Länge enthält.
Kann man ausgehend von einem beliebigen Knoten durch "Umschalten" einer ungeraden Anzahl von (nicht notwendig verschiedenen) Binär-Stellen wieder zum Ausgangsort zurück kommen?
Also...?!
> da ja bei einem Würfel immer wegen [mm]2^n[/mm] immer eine gerade
> Anzahl an
> Ecken herauskommt und nie alle Ecken miteinander in
> Verbindung
> stehen.
> Somit müsste [mm]Q_n[/mm] auch bipartit sein.
Das Ergebnis ist richtig. Alle diese Würfel sind bipartit.
> ii) Hier bin ich von folgender Definition ausgeganngen:
> Ein zusammenhängender Graph besitzt genau dann einen
> Eulerzug,
> wenn alle Knoten geraden Grad haben.
>
> Da [mm]\forall_{a\in V} \ deg(a)=n[/mm] und n immer der Dimension
> entspricht
> folgt für mich:
>
> dass für alle [mm]Q_n[/mm] mit n=ungerade: [mm]Q_n[/mm] keinen Eulerkreis
> besitz
> und für alle [mm]Q_n[/mm] mit n=gerade: [mm]Q_n[/mm] einen Eulerkreis
> besitz.
perfekt richtig!
> iii) Auch hier wieder durch reines einzeichnen in n=1 bis
> n=4 auf alle
> geschlussfolgert:
> für n>1 existiert ein Hamiltonkreis.
>
> iv) und hier hakt es nun gewaltig. Ich habswieder mit
> zeichen versucht
> und bis n=3 geht es super nur bei 4 gibt es kleine
> Lösung naja und da
> alle weiteren drauf aufbauen nehme ich wieder an das es
> auch nicht
> geht.
>
> Beispiele für Hamiltonkreis und Eulerkreis kann ich ja
> angeben
> Aber ich brauch doch einen ordenlichen Beweis und kann
> nicht einfach sagen: "So guckt euch die Zeichnung an, da
> sieht man doch, dass es klar ist."
da hast du vollkommen recht!
Versuche einmal, alle n-stelligen Binärzahlen so anzuordnen, daß sich aufeinanderfolgende nur in einer Stelle unterscheiden und die erste und letzte ebenfalls.
Dann hast du den allgemeinen Hamiltonkreis für den n-dim. Würfel
LG
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:09 Sa 05.01.2008 | | Autor: | Kar_o |
Das macht mir schon mal sehr viel Mut. Denn es zeigt mir, dass wenn ich mal tief in mich gehe und vorallem ein paar Bücher wälze dann scheint es der Anfang doch ganz gut zu kappen.
Trotzdem noch eine Frage zum Anfang:
Also es ist ja eindeutig Variation ich habe zwei Zahlen (n) aus denen ich eine k-elemtige "Kette" aufbauene kann, jede der beiden Zahlen kann ja beliebig oft vorkommen. Das heißt [mm] n^k.
[/mm]
Aber wie drücke ich das jetzt mathematisch korrekt aus?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:24 Sa 05.01.2008 | | Autor: | koepper |
Hallo,
> Also es ist ja eindeutig Variation ich habe zwei Zahlen
> (n) aus denen ich eine k-elemtige "Kette" aufbauene kann,
> jede der beiden Zahlen kann ja beliebig oft vorkommen. Das
> heißt [mm]n^k.[/mm]
>
> Aber wie drücke ich das jetzt mathematisch korrekt aus?
einfach so:
Es gibt [mm] $n^k$ [/mm] Möglichkeiten, aus n Objekten k mal zu ziehen unter Beachtung der Reihenfolge und mit Zurücklegen (d.h. 0en und 1en dürfen wiederholt vorkommen).
Gruß
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:51 Sa 05.01.2008 | | Autor: | Kar_o |
> Versuche mal, deine Wege durch den Würfel weniger graphisch
> zu sehen.
> Stattdessen versuche, sie mal durch "Umschalten von
> Binärstellen" in der Knotendarstellung zu machen.
> Du weißt ja, daß je 2 Knoten verbunden sind, wenn sie sich
> in genau einer Stelle unterscheiden... OK?
> Und dann überlege einfach: Ein Graph ist genau dann
> bipartit, wenn er keinen Kreis ungerader Länge enthält.
> Kann man ausgehend von einem beliebigen Knoten durch
> "Umschalten" einer ungeraden Anzahl von (nicht notwendig
> verschiedenen) Binär-Stellen wieder zum Ausgangsort zurück
> kommen?
> Also...?!
Kann ich dann hier trotzdem die Beispiele bringen, also für n=1 (naja hier existert ja eigentlich kein Kreis aber dieser Graph besteht nur aus zwei ecken)
n=2 00-01-11-10und wieder zurück zu 00
und so weiter und so fort oder muss ich das er in Textform aufschreiben?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:14 Sa 05.01.2008 | | Autor: | koepper |
Hallo,
> Kann ich dann hier trotzdem die Beispiele bringen, also für
> n=1 (naja hier existert ja eigentlich kein Kreis aber
> dieser Graph besteht nur aus zwei ecken)
> n=2 00-01-11-10und wieder zurück zu 00
> und so weiter und so fort oder muss ich das er in Textform
> aufschreiben?
zum eigenen Verständnis sind Beispiele natürlich erstmal angebracht. Aber schließlich mußt du es schaffen, aus den Beispielen ein allgemeines Verfahren für beliebige n zu entwickeln. Dann ist dieses Verfahren darzustellen (das kann auch in Textform geschehen) und zu beweisen, daß es wirklich das geforderte leistet.
Dieser Aufgabenteil ist offensichtlich der bei weitem anspruchsvollste.
Ich würde schon bei den Beispielen versuchen, die Reihenfolge für das nächsthöhere n aus der Reihenfolge für das vorherige zu gewinnen. Dann bietet sich beim Beweis eine Induktion über n an.
Gruß
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:45 Sa 05.01.2008 | | Autor: | Kar_o |
Ich würde schon bei den Beispielen versuchen, die Reihenfolge für das nächsthöhere n aus der Reihenfolge für das vorherige zu gewinnen.
Mir ist klar, dass sich jede Ecke "verdoppelt" , denn es kommt jedes mal ein 1 und eine 0 vornedran z.B. 0-1
0 wird zu 00 und zu 10
1 wird zu 01 und zu 11 und dann werden diese nun entstanden Punkte wieder jeweil zweimal einmal mit null und einemal mit 1 aufgeschrieben, aber mir ist nicht klar wie man das audrückt.
ich glaube das ist genau das problem, dass ich mit dem "Allgemeienen Hamiltonkreis für den n-dim. Würfel habe
mir fällt dabei gerade was ein:
das würde doch heißen, der folgende Graph , also der Nachfolger immer das Doppelte vom Graphen ist, was heißt, dass immer eine gerade anzahl an Ecken dazu kommt bzw. das der bestehende Kreis (gerader Knotenanzahl) wieder ein Keis mit gerader Knotenanzahl wird somit müsste jeder nachfolger auch bipartit sein, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:14 So 06.01.2008 | | Autor: | koepper |
Hallo,
> Mir ist klar, dass sich jede Ecke "verdoppelt" , denn es
> kommt jedes mal ein 1 und eine 0 vornedran z.B. 0-1
> 0 wird zu 00 und zu 10
> 1 wird zu 01 und zu 11 und dann werden diese nun
> entstanden Punkte wieder jeweil zweimal einmal mit null und
> einemal mit 1 aufgeschrieben, aber mir ist nicht klar wie
> man das audrückt.
>
> ich glaube das ist genau das problem, dass ich mit dem
> "Allgemeienen Hamiltonkreis für den n-dim. Würfel habe
Konstruiere einfach mal einen Hamiltonkreis für n=2. Dann überlege, wie man daraus einen Hamiltonkreis für n=3 erhalten kann. Das ist nicht unbedingt offensichtlich, aber da du ja nicht auf den Kopf gefallen bist, wirst du das schaffen.
Tipp: Wie du richtig bemerkt hast, "verdoppelt" sich der Graph für das nächsthöhere n. Konstruiere nun den Hamiltonkreis für dieses n, indem du ausgehend von dem Kreis für das vorherige n geschickt zwischen den beiden (Teil-)Graphen hin und her springst.
> mir fällt dabei gerade was ein:
>
> das würde doch heißen, der folgende Graph , also der
> Nachfolger immer das Doppelte vom Graphen ist, was heißt,
> dass immer eine gerade anzahl an Ecken dazu kommt bzw. das
> der bestehende Kreis (gerader Knotenanzahl) wieder ein Keis
> mit gerader Knotenanzahl wird somit müsste jeder
> nachfolger auch bipartit sein, oder?
yes, alle diese Graphen sind bipartit. Deine Begründung leuchtet mir allerdings nicht so ganz ein. Denn wenn zu einem Kreis mit gerader Länge ein weiterer Kreis mit gerader Länge hinzukommt, dann könnte es durch Verflechtungen der beiden Kreise auch zu einem Kreis mit ungerader Länge kommen.
Begründe es besser so, wie ich in meinen letzten Beiträgen beschrieben hatte (das "Umswitchen" der Bits...). Da du ja Informatiker bist, darf ich es wohl auch mal so ausdrücken:
Könnte man aus einem Bit-Wort a (d.h. ein Knoten) durch eine ungerade Anzahl von XOR-Operationen mit einer 2er-Potenz (und das sind ja Bewegungen von Knoten zu Knoten) wieder zurückkommen zu a?
Gruß
Will
PS: Der Matheraum-Server scheint ziemlich überlastet. Ich bin in den letzten Stunden kaum reingekommen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:54 So 06.01.2008 | | Autor: | Kar_o |
00-01-11-10 --> 000-001-011-010-110-111-101-100
ok ich habs jetzt so weit gefunden, dass man den Hamiltonkreis von n=2 eingentlich bei n=3 auch "abläuft und dann sozusagen bei den Kopien der Punkte den Weg rückwerts geht. und bei n=4 nimmt man dann wieder den kompletten hamiltonkreis von n3 und geht wieder zur "Kopie" und läuft die Punkte wieder nur zurück.
Kann ich das dann folgender Maßen aufschreiben:
[mm] u_1 [/mm] - [mm] v_1 [/mm] - [mm] v_1' [/mm] - [mm] u_1' [/mm] - [mm] u_2' [/mm] - [mm] v_2' [/mm] - [mm] v_2 [/mm] - [mm] u_2 [/mm] - [mm] u_3 [/mm] - [mm] v_3 [/mm] - ... -
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:49 So 06.01.2008 | | Autor: | koepper |
Hallo [mm] Kar_o,
[/mm]
> 00-01-11-10 --> 000-001-011-010-110-111-101-100
>
> ok ich habs jetzt so weit gefunden, dass man den
> Hamiltonkreis von n=2 eingentlich bei n=3 auch "abläuft und
> dann sozusagen bei den Kopien der Punkte den Weg rückwerts
> geht. und bei n=4 nimmt man dann wieder den kompletten
> hamiltonkreis von n3 und geht wieder zur "Kopie" und läuft
> die Punkte wieder nur zurück.
ausgezeichnet!
Damit wissen wir, daß es für alle n>1 einen Hamiltonkreis gibt.
Jetzt gehts an den Beweis: Ich weiß leider nicht, wie ihr in der Vorlesung Wege in Graphen definiert habt. Man kann sie als alternierende Folge von Knoten und Kanten definieren, manche definieren sie aber einfacher als Folge von Knoten. Ich gehe jetzt mal von letzterem aus. Dann kannst du einen Induktionsbeweis führen, indem du einfach einen Hamiltonkreis für n=2 angibst. Dazu gehört allerdings auch der letzte Knoten, der mit dem Anfangsknoten identisch ist. Ansonsten, wie oben.
Dann der Induktionsschritt:
Angenommen es existiert für n=k ein Hamiltonkreis
[mm] $H_k [/mm] = [mm] (v_0, v_1, v_2, \ldots, v_m, v_0).$
[/mm]
Dann erhalten wir einen Hamiltonkreis für $n = k + 1$ durch
[mm] $H_{k+1} [/mm] = [mm] (v_0, v_1, v_2, \ldots, v_m, v_m [/mm] + [mm] 2^k, v_{m-1} [/mm] + [mm] 2^k, \ldots, v_0 [/mm] + [mm] 2^k, v_0).$
[/mm]
Damit existiert ein Hamiltonkreis im n-dimensionalen Würfel für alle n>1.
Das war's. Wenn die Knoten im k-dimensionalen Würfel Binärzahlen der Länge k sind, dann springt die Addition um [mm] $2^k$ [/mm] im k+1-dimensionalen Würfel eben zur "Kopie". OK?
Gruß
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:25 Mi 09.01.2008 | | Autor: | Kar_o |
Wärend ich versucht habe einer Freundin den Hamiltonkreis um Hyperwürfel zu erklären ist mir aufgefallen, dass ich doch noch nicht alles verstanden hab.
1) Als Induktionsanfang gebe ich doch einfach den Hamiltonkreis von n=2 . Aber muss ich nicht irgendwann auch noch zeigen das das was ich im induktonsschritt rausbekomme auch stimmt also z.B von n=2 auf n=3 oder so?
2) warum muss ich n=k nochmal hinschreiben : doch weil ich n einen Wert zuweisen muss, der in dem fall eben ein unbekannter ist. Nun kam die Frage von meiner Freundin warum ich da nicht einfach wieder n nehmen kann? Na ja und da kam ich ins eiern. Würd halt sagen, also [mm] H_k [/mm] das k steht ja nicht für das [mm] Q_n [/mm] sondern für die Anzahl der Knoten v oder? Oder könnte ich da rein theoretisch auch [mm] H_n [/mm] oder sogar [mm] H_Q_n [/mm] schreiben?
3)
> Wenn die Knoten im k-dimensionalen Würfel Binärzahlen der Länge k sind, dann springt die Addition um $ [mm] 2^k [/mm] $ im k+1-dimensionalen Würfel eben zur "Kopie".
Und was mir auch noch nicht so klar ist , du hast geschrieben [mm] v_0, v_1,... v_m,v_m+2^k [/mm] ... durch dieses [mm] +2^k [/mm] soll doch ausgedrückt werden, dass noch eine 0 bzw eine 1 dazu kommt, aber wie ist das dann bei den [mm] v_1 [/mm] bis [mm] v_m [/mm] da muss dann doch auch noch was dazu?
Danke schonmal für deine tolle Hilfe und vorallem für deine Ausdauer :D
Gruß [mm] Kar_o
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:06 Do 10.01.2008 | | Autor: | koepper |
Hallo [mm] Kar_o,
[/mm]
> 1) Als Induktionsanfang gebe ich doch einfach den
> Hamiltonkreis von n=2 . Aber muss ich nicht irgendwann auch
> noch zeigen das das was ich im induktonsschritt rausbekomme
> auch stimmt also z.B von n=2 auf n=3 oder so?
natürlich. Das habe ich hier getan:
Dann der Induktionsschritt:
Angenommen es existiert für n=k ein Hamiltonkreis
$ [mm] H_k [/mm] = [mm] (v_0, v_1, v_2, \ldots, v_m, v_0). [/mm] $
Dann erhalten wir einen Hamiltonkreis für n = k + 1 durch
$ [mm] H_{k+1} [/mm] = [mm] (v_0, v_1, v_2, \ldots, v_m, v_m [/mm] + [mm] 2^k, v_{m-1} [/mm] + [mm] 2^k, \ldots, v_0 [/mm] + [mm] 2^k, v_0). [/mm] $
Damit existiert ein Hamiltonkreis im n-dimensionalen Würfel für alle n>1.
> 2) warum muss ich n=k nochmal hinschreiben : doch weil ich
> n einen Wert zuweisen muss, der in dem fall eben ein
> unbekannter ist.
Mit n=k meinte ich einfach: Die Würfeldimension sei k.
Aber mach dir keine unnötigen Probleme mit diesen Formalitäten. Man kann auch anders formulieren. Ich mach das mal...
Angenommen es existiert ein Hamiltonkreis im n-dimensionalen Würfel
$ [mm] H_n [/mm] = [mm] (v_0, v_1, v_2, \ldots, v_m, v_0). [/mm] $
Dann erhalten wir einen Hamiltonkreis im n+1-dimensionalen Würfel durch
$ [mm] H_{n+1} [/mm] = [mm] (v_0, v_1, v_2, \ldots, v_m, v_m [/mm] + [mm] 2^n, v_{m-1} [/mm] + [mm] 2^n, \ldots, v_0 [/mm] + [mm] 2^n, v_0). [/mm] $
Damit existiert ein Hamiltonkreis im n-dimensionalen Würfel für alle n>1.
Ist das so verständlicher? m ist übrigens immer gleich [mm] $2^n-1$.
[/mm]
> Nun kam die Frage von meiner Freundin
> warum ich da nicht einfach wieder n nehmen kann? Na ja und
> da kam ich ins eiern. Würd halt sagen, also [mm]H_k[/mm] das k steht
> ja nicht für das [mm]Q_n[/mm] sondern für die Anzahl der Knoten v
> oder?
nein, es steht für die Dimension, siehe oben.
> Oder könnte ich da rein theoretisch auch [mm]H_n[/mm]
klar, siehe oben!
> oder sogar [mm]H_Q_n[/mm] schreiben?
das wäre allerdings etwas ungewöhnlich...
Aber es sind ja alles nur Bezeichnungen, und die haben keinen Selbstzweck, sondern dienen nur der Kommunikation von Inhalten. Wenn das erreicht wird, ist es gut 
> 3)
> > Wenn die Knoten im k-dimensionalen Würfel Binärzahlen der
> Länge k sind, dann springt die Addition um [mm]2^k[/mm] im
> k+1-dimensionalen Würfel eben zur "Kopie".
>
> Und was mir auch noch nicht so klar ist , du hast
> geschrieben [mm]v_0, v_1,... v_m,v_m+2^k[/mm] ... durch dieses [mm]+2^k[/mm]
> soll doch ausgedrückt werden, dass noch eine 0 bzw eine 1
> dazu kommt,
genau so ist es, und zwar "ganz vorne".
> aber wie ist das dann bei den [mm]v_1[/mm] bis [mm]v_m[/mm] da
> muss dann doch auch noch was dazu?
ich glaube ich verstehe gerade nicht ganz, was du meinst:
Erst gehen wir von [mm] $v_0$ [/mm] bis [mm] $v_m$, [/mm] dann springen wir zu [mm] $v_m+2^n$ [/mm] und dann weiter "rückwärts" über [mm] $v_{m-1}+2^n$ [/mm] bis [mm] $v_0 [/mm] + [mm] 2^n$ [/mm] und dann zurück zu [mm] $v_0$.
[/mm]
> Danke schonmal für deine tolle Hilfe und vorallem für deine Ausdauer :D
mache ich sehr gerne, wenn ich sehe, daß jemand versucht, etwas wirklich zu verstehen - wie du, und es nicht bloß um Ergebnisse geht.
LG
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:21 Do 10.01.2008 | | Autor: | Kar_o |
na ja eigentlich müsste ich doch an die [mm] v_0,v_1,v_2,....,v_m [/mm] eine Null vorne dran schreiben und bei [mm] v_m+2^n,v_{m-1}+2^n,... [/mm] eine 1 .
Na und jetzt schreibe ich aber nur bei [mm] v_m+2^n,... [/mm] diese [mm] 2^n [/mm] dran also die "1" dazu ...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:20 Do 10.01.2008 | | Autor: | koepper |
Hallo,
> na ja eigentlich müsste ich doch an die
> [mm]v_0,v_1,v_2,....,v_m[/mm] eine Null vorne dran schreiben
ja genau, aber da das Hinzufügen der Null vorne nichts am Binärwert ändert, identifizieren wir die Knoten im alten n-dimensionalen Würfel mit diesen Knoten im neuen n+1-dimensionalen Würfel.
> und bei [mm]v_m+2^n,v_{m-1}+2^n,...[/mm] eine 1 .
>
> Na und jetzt schreibe ich aber nur bei [mm]v_m+2^n,...[/mm] diese
> [mm]2^n[/mm] dran also die "1" dazu ...
nein, das machen wir natürlich bei allen weiteren Knoten. siehe auch mein letzter Beitrag.
Gruß
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:36 Mo 07.01.2008 | | Autor: | Kar_o |
Und wie beweise ich jetzt, dass alle [mm] Q_n [/mm] mit n>3 nicht planar sind? Kann ich das einfach durch Zeichnen beweisen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:55 Di 08.01.2008 | | Autor: | koepper |
Hallo [mm] Kar_o,
[/mm]
es gibt da einen nützlichen Satz zu Planarität:
Ein schlichter Graph ist genau dann planar, wenn er weder den vollständigen Graphen [mm] $V_5$ [/mm] noch den vollständig bipartiten Graphen [mm] $B_{3,3}$ [/mm] enthält. Wenn du also Nicht-Planarität nachweisen willst, solltest du einen dieser beiden Graphen in deinem Würfel suchen.
Gruß
Will
|
|
|
|
