Меню Главная Случайная статья Настройки Граф Кауца Материал из https://ru.wikipedia.org Граф Кауца ${\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}}$. Графы Кауца тесно связаны с графами де Брёйна. Содержание 1 Свойства 2 В обработке данных 3 Примечания 4 Литература Свойства Для фиксированной степени ${\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], такие сети известны как сети Кауца. Примечания Darcy, 2007. Li, Lu, Su, 2004, с. 308–315. Литература Jeff Darcy. The Kautz Graph. — Canned Platypus, 2007. Dongsheng Li, Xicheng Lu, Jinshu Su. Network and Parallel Computing: IFIP International Conference. — Wuhan, China: NPC, 2004. — ISBN 3-540-23388-1.