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

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

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

Свойства

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

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

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

Примечания

Литература