Граф Кауца

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

Граф Кауца $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\ne s_{i+1}$).

Граф Кауца $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\ne 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$.

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

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