# Differences

This shows you the differences between two versions of the page.

Both sides previous revision Previous revision Next revision | Previous revision | ||

hypercube_graph [2014/02/10 23:14] nikolaj |
hypercube_graph [2014/03/21 11:11] (current) |
||
---|---|---|---|

Line 1: | Line 1: | ||

===== Hypercube graph ===== | ===== Hypercube graph ===== | ||

==== Set ==== | ==== Set ==== | ||

- | | @#88DDEE: $ n\in\mathbb N, n\ge 1 $ | | + | | @#55CCEE: context | @#55CCEE: $ n\in\mathbb N, n\ge 1 $ | |

- | | @#DDDDDD: $ V\equiv \{0,1\}^n $ | | + | | @#DDDDDD: range | @#DDDDDD: $ V\equiv \{0,1\}^n $ | |

- | | @#FFBB00: $Q_n\equiv \langle V,E\rangle$ | | + | | @#FFBB00: definiendum | @#FFBB00: $Q_n\equiv \langle V,E\rangle$ | |

- | | @#DDDDDD: $ k\in\mathbb N,1\le k\le n $ | | + | | @#DDDDDD: range | @#DDDDDD: $ k\in\mathbb N,1\le k\le n $ | |

- | | @#FFFDDD: $ v,w\in V $ | | + | | @#FFFDDD: for all | @#FFFDDD: $ v,w\in V $ | |

- | | @#55EE55: $ \{v,w\}\in E\leftrightarrow \exists!k.\ \pi_k(v)\neq\pi_k(w) $ | | + | | @#55EE55: postulate | @#55EE55: $ \{v,w\}\in E\leftrightarrow \exists!k.\ \pi_k(v)\neq\pi_k(w) $ | |

==== Discussion ==== | ==== Discussion ==== | ||

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 ==== | ||

=== Subset of === | === Subset of === | ||

[[k-regular graph]], [[Bipartite graph]] | [[k-regular graph]], [[Bipartite graph]] | ||

- | === Requirements === | + | === Context === |

[[Cartesian product]] | [[Cartesian product]] |