Граф Кауца

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

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

Граф Кауца [math]\displaystyle{ K_M^{N + 1} }[/math] имеет [math]\displaystyle{ (M + 1)M^{N + 1} }[/math] рёбер

[math]\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} \} \, }[/math]

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

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

Свойства

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

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

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