suche Beweis de Bruijn Sequenz

Neue Frage »

brainder Auf diesen Beitrag antworten »
suche Beweis de Bruijn Sequenz
Meine Frage:
Hallo allerseits!
Ich soll einen Beweis dafür finden, dass für jedes n eine zirkuläre Folge der Länge 2n existiert in der alle n-stelligen Binärzahlen
genau einmal vorkommen. (es geht um Binärzahlen)
Nun ja, ich habe schon herausgefunden, dass es diese Sequenzen gibt und wofür sie verwendet werden:
http://en.wikipedia.org/wiki/De_Bruijn_sequence
http://mathworld.wolfram.com/deBruijnSequence.html

Aber ich verstehe nicht ganz wie ich das beweisen soll/kann.


Meine Ideen:
Ein Gedanke war es mit vollständiger Induktion zu zeigen, jedoch bin ich mir nicht sicher ob/wie das hier funktioniert.
Mystic Auf diesen Beitrag antworten »
RE: suche Beweis de Bruijn Sequenz
Hm, ich vermute, du hast das, was in dem von dir zitierten Wikipedia-Artikel dazu steht nicht verstanden, insbesondere dass es nur darum geht, in dem Graphen, welcher dort in dem Beispiel für n=4 abgebildet ist, eine Euler-Tour zu finden... Die gibt es aber trivialerweise, da ja der Hin- und Wegrad für jeden Knoten 2, also gleich ist...
brainder Auf diesen Beitrag antworten »
RE: suche Beweis de Bruijn Sequenz
doch, das hab ich schon verstanden.
Aber wie zeigt man, dass allgemein für n diese Sequenz eine Länge von 2^n hat? (da habe ich vorher das "^" vergessen)
Mystic Auf diesen Beitrag antworten »
RE: suche Beweis de Bruijn Sequenz
Naja, immerhin sollte ja jedes Binärwort der Länge n genau einmal in der Sequenz vorkommen... Man könnte also die Frage auch so stellen: Wieviele Binärwörter der Länge n gibt es?...
brainder Auf diesen Beitrag antworten »

2^n natürlich, aber zu sagen es gibt 2^n n-stellige Binärzahlen, erklärt mir weder die Länge der Sequenz, noch ist es ein Beweis dafür, dass es diese Sequenz für alle n gibt.
ich hab so das Gefühl, ich steh auf der Leitung...
Mystic Auf diesen Beitrag antworten »

Ich denke, wir reden einfach aneinander vorbei... Nehmen wir doch einfach das Beispiel n=4, welches in dem von dir verlinkten Artikiel sehr sauber durchgerechndet ist, sodass eigentlich keine Fragen offenbleiben sollten...

Schau dir den Graphen dazu an, dessen Eckpunkte alle Binärtripel sind, also gibt es 8 Knoten... Die Binärsequenz, welche hier gesucht ist, besteht aber aus den Kanten(!!!) dieses Graphen (lies dir den Text zu dem Beispiel durch, ich glaube, es ist gerade dieser Punkt, den du bisher nicht verstanden hast!), d.h., du brauchst nur diese abzählen... Da in der Adjazenzmatrix in jeder Zeile 2 Einsen sind, ist die Summe der Einträge doppelt so groß wie die Anzahl der Knoten, also 16... Allgemein ist die Anzahl der Kanten (=Anzahl der Glieder in der Binärsequenz) immer doppelt so groß wie die Anzahl der Knoten und diese beträgt ja offensichtlich ...
 
 
brainder Auf diesen Beitrag antworten »

danke, jetzt hab ichs verstanden.
du hattest recht, ich hab den Teil mit dem Eulerkreis irgendwie mit Hamilton durcheinandergebracht
Neue Frage »
Antworten »



Verwandte Themen

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