Граф Каутца

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

Граф Каутца - это ориентированный граф степени и размерности , вершины которого помечены всеми возможными строками длины , состоящими из символов, выбранных из алфавита, содержащего различные символы, при условии, что соседние символы в строке не могут быть равными ( ) .${\ 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_ {я} \ neq s_ {я + 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}$

В вычислениях [ править ]

Граф Каутца использовался в качестве сетевой топологии для соединения процессоров в приложениях высокопроизводительных вычислений ^[1] и отказоустойчивых вычислений ^[2] : такая сеть известна как сеть Каутца .

Заметки [ править ]

Эта статья включает материал из графика Каутца на PlanetMath , который находится под лицензией Creative Commons Attribution / Share-Alike License .