Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | |||
|
hypercube_graph [2014/02/10 23:14] nikolaj |
hypercube_graph [2014/02/10 23:22] nikolaj |
||
|---|---|---|---|
| Line 14: | Line 14: | ||
| The Hypercube graph, also called n-cube, has vertices all n-tuples of 0's and 1's and two such vertices are connected iff they differ in one coordinate. | The Hypercube graph, also called n-cube, has vertices all n-tuples of 0's and 1's and two such vertices are connected iff they differ in one coordinate. | ||
| + | Since strings with 0's and 1's of length $n$ encode the subsetsets of an n-element set, we have $|V|=2^n$. And since for each n-tuple there $n$ ways to differ from it by one digit, there are $\frac{1}{2}2^n\cdot n$ vertices. | ||
| + | |||
| + | It is also the Hesse diagram of a Boolean lattice, the powerset with elements connected iff they differ by one element. | ||
| + | === Examples === | ||
| E.g. $V(Q_2)=\{\langle 0,0\rangle,\langle 0,1\rangle,\langle 1,0\rangle,\langle 1,1\rangle\}$ and there are all but the diagonal relations are edges in the graph. Clearly $Q_n$ is just a square. | E.g. $V(Q_2)=\{\langle 0,0\rangle,\langle 0,1\rangle,\langle 1,0\rangle,\langle 1,1\rangle\}$ and there are all but the diagonal relations are edges in the graph. Clearly $Q_n$ is just a square. | ||
| ==== Parents ==== | ==== Parents ==== | ||
