summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/tkz/tkz-berge/NamedGraphs/doc/latex/NamedGraphs-Hypercube.tex
blob: f13cca73bc72a5a847a0cc2c54825be8296bb219 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
\newpage\section{Hypercube}
%<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––>
%<––––––––––––––––––––  Hypercube            –––––––––––––––––––––––––––––––>
%<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––>
From Wikipedia :\url{http://en.wikipedia.org/wiki/Hypercube_graph}

In the mathematical field of graph theory, the hypercube graph $Q_n$ is a  special regular graph with $2n$ vertices, which correspond to the subsets of a set with $n$ elements. Two vertices labelled by subsets S and T are joined by an edge if and only if S can be obtained from T by adding or removing a single element. Each vertex of $Q_n$ is incident to exactly $n$ edges (that is, $Q_n$ is $n$-regular), so the total number of edges is $2^{n-1}n$.
The name comes from the fact that the hypercube graph is the one-dimensional skeleton of the geometric hypercube.
Hypercube graphs should not be confused with cubic graphs, which are graphs that are 3-regular. The only hypercube that is a cubic graph is $Q_3$.

\tikzstyle{VertexStyle}       = [shape        = circle,%
                                 fill         = red,%
                                 inner sep    = 3pt,%
                                 outer sep    = 0pt,%
                                 draw]
\SetVertexNoLabel

\subsection{\tkzname{The hypercube graph $Q_4$} }

The code is on the next page.

\begin{center}
\begin{tkzexample}[vbox]
\begin{tikzpicture}[scale=.75]
  \grCycle[RA=8]{8}
  \pgfmathparse{8*(1-4*sin(22.5)*sin(22.5))}
  \let\tkzbradius\pgfmathresult
  \grCirculant[prefix=b,RA=\tkzbradius]{8}{3}
  \makeatletter
  \foreach \vx in {0,...,7}{%
    \pgfmathsetcounter{tkz@gr@n}{mod(\vx+1,8)}
    \pgfmathsetcounter{tkz@gr@a}{mod(\vx+7,8)}
    \pgfmathsetcounter{tkz@gr@b}{mod(\thetkz@gr@n+1,8)}
    \Edge(a\thetkz@gr@n)(b\thetkz@gr@b)
    \Edge(b\thetkz@gr@a)(a\vx)
    }
  \makeatother
\end{tikzpicture}
\end{tkzexample}
\end{center}
\endinput