Граф Кауца

Граф Кауца ${\displaystyle K_{M}^{N+1}}$ — это ориентированный граф степени ${\displaystyle M}$ и размерности ${\displaystyle N+1}$, который имеет ${\displaystyle (M+1)M^{N}}$ вершин, помеченных всеми возможными строками ${\displaystyle s_{0}\cdots s_{N}}$ длины ${\displaystyle N+1}$, которые составлены из символов ${\displaystyle s_{i}}$, выбранных из алфавита ${\displaystyle A}$, содержащего ${\displaystyle M+1}$ различных символов с условием, что соседние символы не могут совпадать (${\displaystyle s_{i}\neq s_{i+1}}$).

Пример графа Кауца на 3 символах с длиной строк 2 (слева) и 3 (справа). Рёбра слева соответствуют вершинам справа.

Граф Кауца ${\displaystyle K_{M}^{N+1}}$ имеет ${\displaystyle (M+1)M^{N+1}}$ рёбер

${\displaystyle \{(s_{0}s_{1}\cdots s_{N},s_{1}s_{2}\cdots s_{N}s_{N+1})|\;s_{i}\in A\;s_{i}\neq s_{i+1}\}\,}$

Естественно пометить каждое такое ребро ${\displaystyle K_{M}^{N+1}}$ как ${\displaystyle s_{0}s_{1}\cdots s_{N+1}}$, создавая один-к-одному соответствие между рёбрами графа Кауца ${\displaystyle K_{M}^{N+1}}$ и вершинами графа Кауца ${\displaystyle K_{M}^{N+2}}$.

Графы Кауца тесно связаны с графами де Брёйна.