График Каутца

Пример графа Каутца на 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}\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}$

В вычислительной технике

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

Примечания

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

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