Граф Каутца - Kautz graph

Пример Граф Каутца по 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_{i}eq 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}eq 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] приложения: такая сеть известна как Сеть Каутц.

Примечания

1. Дарси, Джефф (31 декабря 2007 г.). "Граф Каутца". Консервированный утконос. Внешняя ссылка в | publisher = (Помогите)
2. Ли, Дуншэн; Сичэн Лу; Цзиньшу Су (2004). "Теоретико-графический анализ топологии Каутца и схем DHT". Сети и параллельные вычисления: Международная конференция IFIP. Ухань, Китай: NPC. С. 308–315. ISBN  3-540-23388-1. Получено 2008-03-05.

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