Граф Кауца

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

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

{ ( s 0 s 1 ⋯ s N , s 1 s 2 ⋯ s N s N + 1 ) | s i ∈ A s i ≠ s i + 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} eq s_{i+1}},}

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

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

Свойства

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

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

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