Würfelgraph konstruieren < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Wie bekommt man die Elemente der Menge für den Würfelgraphen Qn?
Im Skript steht:
Der Würfelgraph Qn entsteht auf folgende Weise: Als Knotenmenge V wählt man die [mm] 2^n [/mm] -elementige Menge alle n-stelligen 0,1 Folgen.
Allerdings finde ich keine Erklärung zu n-stelligen Funktionen.
Für Q3 könnte man binär hochzählen von 000-111. Klappt das auch bei Qn?
|
|
| |
|
> Wie bekommt man die Elemente der Menge für den
> Würfelgraphen Qn?
>
>
> Im Skript steht:
> Der Würfelgraph Qn entsteht auf folgende Weise: Als
> Knotenmenge V wählt man die [mm]2^n[/mm] -elementige Menge alle
> n-stelligen 0,1 Folgen.
>
>
> Allerdings finde ich keine Erklärung zu n-stelligen
> Funktionen.
>
>
> Für Q3 könnte man binär hochzählen von 000-111. Klappt
> das auch bei Qn?
Ja.
|
|
|
| |
|
Also hat der Würfelgraph Q4 16 Knoten:
V = {0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111}
und diese Kanten:
E = {
{0000,0001},{0000,0010},{0000,0100},{0000,1000}
{0001,1001},{0001,0011}
{0010,0011},{0010,0110},{0010,1010}
{0011,0111},{0011,1011}
{0100,0101},{0100,0110},{0100,1100}
{0101,0111},{0101,1101}
{0110,0111},{0110,1110}
{0111,1111}
{1000,1001}{1000,1010}
{1001, ??? }
{1010,1011}
{1011,1111}
{1100,1101}
{1101,1111}
{1110,1111}
{1111, ??? }
}
Diese Katen weil: Zwei Knoten werden genau dann durch eine Kante verbunden, wenn sich die entsprechenden Folgen
an genau einer Stelle unterscheiden.
Oder hab ich die Aussage falsch interpretiert?
|
|
|
| |
|
Hallo,
> Also hat der Würfelgraph Q4 16 Knoten:
>
> V =
> {0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111}
![[ok]](/images/smileys/ok.gif "[ok]")
>
> und diese Kanten:
> E = {
> {0000,0001},{0000,0010},{0000,0100},{0000,1000}
> {0001,1001},{0001,0011}
> {0010,0011},{0010,0110},{0010,1010}
> {0011,0111},{0011,1011}
> {0100,0101},{0100,0110},{0100,1100}
> {0101,0111},{0101,1101}
> {0110,0111},{0110,1110}
> {0111,1111}
> {1000,1001}{1000,1010}
> {1001, ??? }
> {1010,1011}
> {1011,1111}
> {1100,1101}
> {1101,1111}
> {1110,1111}
> {1111, ??? }
> }
Die Kantenmenge stimmt nicht:
Jeder Knoten ist zu genau 4 Kanten inzident und insgesamt gibt es [mm] 2^4=16 [/mm] Knoten. Damit haben wir [mm] \frac{4*16}{2}=32 [/mm] Kanten (Doppeltes Abzaehlen).
>
> Diese Katen weil: Zwei Knoten werden genau dann durch eine
> Kante verbunden, wenn sich die entsprechenden Folgen
> an genau einer Stelle unterscheiden.
LG
|
|
|
| |
|
> Hallo,
>
> > Also hat der Würfelgraph Q4 16 Knoten:
> >
> > V =
> >
> {0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111}
>
> >
> > und diese Kanten:
> > E = {
> > {0000,0001},{0000,0010},{0000,0100},{0000,1000}
> > {0001,1001},{0001,0011}
> > {0010,0011},{0010,0110},{0010,1010}
> > {0011,0111},{0011,1011}
> > {0100,0101},{0100,0110},{0100,1100}
> > {0101,0111},{0101,1101}
> > {0110,0111},{0110,1110}
> > {0111,1111}
> > {1000,1001}{1000,1010}
> > {1001, ??? }
> > {1010,1011}
> > {1011,1111}
> > {1100,1101}
> > {1101,1111}
> > {1110,1111}
> > {1111, ??? }
> > }
> Die Kantenmenge stimmt nicht:
>
> Jeder Knoten ist zu genau 4 Kanten adjazent und insgesamt
> gibt es [mm]2^4=16[/mm] Knoten. Damit haben wir [mm]\frac{4*16}{2}=32[/mm]
> Kanten (Doppeltes Abzaehlen).
Das heisst also das bei einem Q6, jeder Knoten zu 6 Kanten adjazent ist?
Die doppelten hatte ich jetzt nicht mit aufgezählt. Also wenn 0000,0001 da war habe ich 0001,0000 nicht aufgeschrieben. Hier ist die komplette Auflistung:
E = {
{0000,0001},{0000,0010},{0000,0100},{0000,1000}
{0001,1001},{0001,0011},{0001,0000},{0001,0101}
{0010,0011},{0010,0110},{0010,1010},{0010,1010}
{0011,0111},{0011,1011},{0011,0001},{0011,0010}
{0100,0101},{0100,0110},{0100,1100},{0100,0000}
{0101,0111},{0101,1101},{0101,0001},{0101,0100}
{0110,0111},{0110,1110},{0110,0100},{0110,0010}
{0111,1111},{0111,0110},{0111,0101},{0111,0011}
{1000,1001},{1000,1010},{1000,0000},{1000,1100}
{1001,1000},{1001,0001},{1001,1101},{1001,1011}
{1010,1011},{1010,1110},{1010,1000},{1010,0010}
{1011,1111},{1011,1010},{1011,0011},{1011,1001}
{1100,1101},{1100,1110},{1100,0100},{1100,1000}
{1101,1111},{1101,1001},{1101,0101},{1101,1100}
{1110,1111},{1110,1100},{1110,0110},{1110,1010}
{1111,1110},{1111,0111},{1111,1011},{1111,1101}
}
|
|
|
| |
|
Moin,
> > Die Kantenmenge stimmt nicht:
> >
> > Jeder Knoten ist zu genau 4 Kanten adjazent und insgesamt
> > gibt es [mm]2^4=16[/mm] Knoten. Damit haben wir [mm]\frac{4*16}{2}=32[/mm]
> > Kanten (Doppeltes Abzaehlen).
>
> Das heisst also das bei einem Q6, jeder Knoten zu 6 Kanten
> inzident ist?
Ja.
>
> Die doppelten hatte ich jetzt nicht mit aufgezählt. Also
> wenn 0000,0001 da war habe ich 0001,0000 nicht
> aufgeschrieben.
Das ist auch okay so, trotzdem fehlten bei dir in der Menge Kanten.
> Hier ist die komplette Auflistung:
>
> E = {
> {0000,0001},{0000,0010},{0000,0100},{0000,1000}
> {0001,1001},{0001,0011},{0001,0000},{0001,0101}
> {0010,0011},{0010,0110},{0010,1010},{0010,1010}
> {0011,0111},{0011,1011},{0011,0001},{0011,0010}
> {0100,0101},{0100,0110},{0100,1100},{0100,0000}
> {0101,0111},{0101,1101},{0101,0001},{0101,0100}
> {0110,0111},{0110,1110},{0110,0100},{0110,0010}
> {0111,1111},{0111,0110},{0111,0101},{0111,0011}
> {1000,1001},{1000,1010},{1000,0000},{1000,1100}
> {1001,1000},{1001,0001},{1001,1101},{1001,1011}
> {1010,1011},{1010,1110},{1010,1000},{1010,0010}
> {1011,1111},{1011,1010},{1011,0011},{1011,1001}
> {1100,1101},{1100,1110},{1100,0100},{1100,1000}
> {1101,1111},{1101,1001},{1101,0101},{1101,1100}
> {1110,1111},{1110,1100},{1110,0110},{1110,1010}
> {1111,1110},{1111,0111},{1111,1011},{1111,1101}
> }
Das kann man so schreiben: In dieser Menge sind 32 Elemente, da jeweils zwei Elemente identisch sind.
>
>
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:42 Fr 18.11.2011 | | Autor: | studentxyz |
Ok, Danke.
|
|
|
|
