Граф Кауца

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

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

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

$\{(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}\}\,$

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

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

Свойства

• Для фиксированной степени $M$ и числа вершин $V=(M+1)M^{N}$ граф Кауца имеет наименьший диаметр для любого ориентированного графа с $V$ вершинами и степенью $M$.
• Все графы Кауца имеют эйлеровы циклы. (Эйлеров цикл — это цикл, который посещает каждое ребро ровно раз — этот результат следует из того, что графы Кауца имеют полустепень захода равную полустепени исхода для каждого узла).
• Все графы Кауца имеют гамильтонов цикл (Этот результат следует из соответствия, описанного выше между рёбрами графа Кауца $K_{M}^{N}$ и вершинами графа Кауца $K_{M}^{N+1}$. Гамильтонов цикл на $K_{M}^{N+1}$ задаётся эйлеровым циклом на $K_{M}^{N}$).
• Граф Кауца степени $k$ имеет $k$ непересекающихся пути из любого узла $x$ в любой другой узел $y$.

В обработке данных

Граф Кауца использовался в качестве сетевой технологии для соединения процессоров в высокопроизводительных вычислениях и отказоустойчивых вычислениях, такие сети известны как сети Кауца.