Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
finite_undirected_graph [2014/02/10 23:09] nikolaj |
finite_undirected_graph [2014/02/10 23:11] nikolaj old revision restored (2014/02/08 00:08) |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ===== Hypercube graph ===== | + | ===== Finite undirected graph ===== |
==== Set ==== | ==== Set ==== | ||
- | | @#88DDEE: $ n\in\mathbb N, n\ge 1 $ | | + | | @#88DDEE: $V,E$ ... set | |
- | | @#DDDDDD: $ V\equiv \{0,1\}^n $ | | + | |
- | | @#FFBB00: $Q_n\equiv \langle V,E\rangle$ | | + | | @#FFBB00: $ \langle V,E,\psi\rangle \in \mathrm{it}(E,V) $ | |
- | | @#DDDDDD: $ k\in\mathbb N,1\le k\le n $ | | + | | @#55EE55: $\langle V,E,\psi\rangle $ ... undirected graph | |
- | | @#FFFDDD: $ v,w\in V $ | | + | | @#55EE55: $ E,V $ ... finite | |
- | + | ||
- | | @#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. | ||
- | |||
- | 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 === | ||
[[Undirected graph]] | [[Undirected graph]] | ||
- | === Requirements === | ||
- | [[Cartesian product]] |