Würfelgraph/Dimension d/Beispiel

Der Würfelgraph zu ${}d=3$. Es ist klar, woher die Bezeichnung kommt.

Der gleiche Graph, aber ohne Überkreuzungen gezeichnet.

Sei ${}d\in \mathbb {N}$. Unter dem ${}d$-dimensionalen Würfelgraphen versteht man die Knotenmenge bestehend aus den ${}d$-Tupeln

$(\pm ,\ldots ,\pm ),$

bei der zwei Punkte genau dann durch eine Kante verbunden werden, wenn sie sich in genau einer Komponente unterscheiden. Statt Würfelgraph sagt man auch Hyperwürfel.