Differences

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

Link to this comparison view

hypercube_graph [2014/02/10 23:14]
nikolaj
hypercube_graph [2014/03/21 11:11]
Line 1: Line 1:
-===== Hypercube graph ===== 
-==== Set ==== 
-| @#88DDEE: $ n\in\mathbb N, n\ge 1 $ | 
-| @#DDDDDD: $ V\equiv \{0,1\}^n $ | 
  
-| @#FFBB00: $Q_n\equiv \langle V,E\rangle$ | 
- 
-| @#DDDDDD: $ k\in\mathbb N,1\le k\le n $ | 
-| @#FFFDDD: $ v,w\in V $ | 
- 
-| @#55EE55: $ \{v,w\}\in E\leftrightarrow \exists!k.\ \pi_k(v)\neq\pi_k(w) $ | 
- 
-==== 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 ==== 
-=== Subset of === 
-[[k-regular graph]], [[Bipartite graph]] 
-=== Requirements === 
-[[Cartesian product]] 
Link to graph
Log In
Improvements of the human condition