N-Cube graph

[math]\displaystyle{ n }[/math]-Cube graph — куб [math]\displaystyle{ n }[/math]-мерный.

Consider the set [math]\displaystyle{ Q^{n} = \{(x_{1}, x_{2}, \ldots, x_{n})| \; x_{i}\in \{0,1\}, \; i = 1, \ldots, n\} }[/math]. For [math]\displaystyle{ u,v \in Q^{n} }[/math] the Hamming distance [math]\displaystyle{ \rho(u,v) }[/math] is defined as the number of entries where [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] differ. An [math]\displaystyle{ n }[/math]-cube graph is a graph on the vertex set [math]\displaystyle{ Q^{n} }[/math], where two vertices [math]\displaystyle{ u, v }[/math] are adjacent iff [math]\displaystyle{ \rho(u,v) = 1 }[/math]. The [math]\displaystyle{ n }[/math]-cube graph is a regular graph with a degree [math]\displaystyle{ n-1 }[/math].

Other names are Hypercube, [math]\displaystyle{ n }[/math]-Dimensional hypercube.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.