Graphentheorie Grundlagen - Hypercubes?
Hallo Freunde.
Ich verstehe bei Graphentheorie - Hypercubes nicht, wie man die Menge V und die menge N bestimmt. Ich verstehe den Text unten irgendwie verwirrend. Auf YouTube finde ich auch keine Videos, die das gut erklären. Könnt ihr mir vielleicht helfen? Ich danke euch.
Welche Menge N?
Sorry. Ich meinte die Menge E. Also wie bestimmt man die Menge der Knoten und die Menge der Kanten.
2 Antworten
Du nummerierst die Knoten binär, wobei jede binäre Stelle einer Dimension entspricht.
Das ist auf der Abbildung auch deutlich zu sehen. Da jede Dimension einer "Bewegungsrichtung" entspricht, wird genau zwischen diese Paaren eine Kante gesetzt, also am Quadrat: 00 01, 00 10, 10 11, 01 11.
Und so setzt sich das als rekursive Struktur entsprechend fort. Jeder Hyperwürfel der Dimension d, entsteht aus 2 Hyperwürfeln der Dimension d-1, wobei die in der neuen Dimension gegenüberliegenden Knoten (unterscheiden sich im Bit der Dimension) verbunden werden.
Wenn Du Dir die Abbildung anschaust:
Nehme ich Q1 und zeichne nochmal Q1 links daneben, schreibe bei der linken Kopie eine führende 0 (bei den Knotenbezeichnern) davor, rechts eine führende 1 und ergänze die fehlenden Kanten entlang der neue vorderen Stelle, so erhalte ich Q2.
Habe ich alles schon erklärt, betrachte doch die Konstruktion von Q1 nach Q2 bzw. Q2 nach Q3 - Das geht dann beliebig weiter, auch wenn es nicht mehr so recht in unsere Vorstellung passt.
Für Q2 sind die Knoten 00, 01, 10, 11 (0,1,2,3) als Binärzahlen betrachtet.
Welche unterscheiden sich genau in 1 Stelle? 00 ändere ich die hintere Stelel komme ich zu 01, ändere ich stattdessen die vordere, komme ich zu 10, also gehören die Paarungen 00 01, 00 10 schonmal dazu. wenn ich bei 10 die hintere Stelle ändere komme ich zu 11, ebenso wenn ich bei 01 die vordere Stelle flippe, hieraus ergibt sich 11 10 sowie 11 01 als KAnten.
-------
Generalisiert:
x1 x2 x3 x4 0 x6
x1 x2 x3 x4 1 x6
Für alle identischen Belegungen der Komponenten xi erhalte ich eine Kante zwischen Knoten, die sich nur in der Stelle d unterscheiden.
Das sind die k-Tupel, die nur aus Nullen und Einsen bestehen.
V
1 0, 1
2 00, 01, 10, 11
3 000, 001, 010, 011, 100, 101, 110, 111
Dabei ist 000 eine platzsparendere Schreibweise für (0,0,0) usw. Du kannst Dir das als Einheitswürfel vorstellen, die erste Komponente ist die x-Koordinate, die zweite die y und die dritte die z. Bei höheren Dimensionen kann man das nur nicht räumlich darstellen. Bei einer Kante kann man für jede der k-Dimensionen 1 in die positive Richtung und 1 in die negative Richtung gehen. Im Dreidimensionalen sind das rechts, links, oben, unten, vor und hinter. Man addiert oder subtrahiert (0,0,1), (0,1,0) oder (1,0,0) und erhält einen anderen Punkt. Wenn an einer Stelle eine 0 steht kann man da höchstens 1 addieren und wenn an einer Stelle eine 1 steht kann man da höchstens 1 abziehen, sonst wäre man nicht mehr im Würfel. Die Kanten sind also Verbindungen von Ecken, die sich an genau einer Koordinate um 1 unterscheiden.
Das steht ja auch noch: Die Menge V bestehe aus allen k-stelligen Binärzahlen, .... Sowie: Die Menge E wird aus allen ungeordneten Paaren von Elementen u, v Element von V gebildet, die sich ab genau dieser Stelle unterscheiden. Was versteht man darunter, also wie genau berechne ich die Menge V und die Menge E.