Hypercube graph
Set
| context | n∈N,n≥1 |
| range | V≡{0,1}n |
| definiendum | Qn≡⟨V,E⟩ |
| range | k∈N,1≤k≤n |
| for all | v,w∈V |
| postulate | {v,w}∈E↔∃!k. πk(v)≠π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.
Since strings with 0's and 1's of length n encode the subsetsets of an n-element set, we have |V|=2n. And since for each n-tuple there n ways to differ from it by one digit, there are 122n⋅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(Q2)={⟨0,0⟩,⟨0,1⟩,⟨1,0⟩,⟨1,1⟩} and there are all but the diagonal relations are edges in the graph. Clearly Qn is just a square.
Parents
Subset of
Context
