n-dimensinale hypercubuse < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:49 Di 15.05.2007 | | Autor: | Frido22 |
| Aufgabe | | Für eine ganze Zahl n [mm] \ge [/mm] 1 ist der n-dimensionale Hypercubus [mm] H_{n} [/mm] duch V [mm] H_{n} [/mm] = {0,1} [mm] x^{n} [/mm] und E [mm] H_{n} [/mm] = {{v,w} : [mm] \parallel [/mm] v-w [mm] \parallel [/mm] = 1} gegeben (zwei Ecken sind benachbart, wenn sie sich nur in einer Komponente unterscheiden). Zeigen Sie, dass jede Ecke Grad n hat. Zeigen Sie, dass |V [mm] H_{n} [/mm] | = [mm] 2^{n} [/mm] und |E [mm] H_{n} [/mm] | = n [mm] 2^{n-1} [/mm] gilt. |
?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Grad:
Ein Würfel ist symmetrisch, es genügt also, nur eine Ecke zu betrachten, oBdA den Nullpunkt.
Wieviele Kanten gehen vom Nullpunkt aus? Warum? Tipp: Wie lauten die Koordinaten der Punkte, die mit dem Nullpunkt direkt verbunden sind?
Anzahl der Ecken und Kanten:
Würde ich vollständige Induktion vorschlagen. Beginnend mit der Strecke (dim=1) sollte das nicht zu schwer sein. Von der Strecke über das Quadrat zum Würfel kannst du alle relevanten Mechanismen beobachten - musst nur noch verallgemeinern.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:28 Mi 23.05.2007 | | Autor: | Frido22 |
hm, ich kann damit leider nicht soviel anfangen...:(
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:50 Mi 23.05.2007 | | Autor: | wauwau |
n-dimensionaler Einheitswürfel
jede V hat die Koordinaten [mm] (x_1,x_2,....,x_n) [/mm] mit [mm] x_i \in [/mm] {0,1} daher [mm] 2^n [/mm] Ecken
jeder dieser Ecken hat Grad n daher [mm] n*2^n [/mm] Kanten, die damit allerdings doppelt gezählt wurden (auf beiden Ecken der Kanten daher [mm] \bruch{n2^n}{2}=n*2^{n-1} [/mm] Kanten
|
|
|
|
