Граф Кауца
Перейти к навигации
Перейти к поиску
Граф Кауца — это ориентированный граф степени и размерности , который имеет вершин, помеченных всеми возможными строками длины , которые составлены из символов , выбранных из алфавита , содержащего различных символов с условием, что соседние символы не могут совпадать ().
Граф Кауца имеет рёбер
Естественно пометить каждое такое ребро как , создавая один-к-одному соответствие между рёбрами графа Кауца и вершинами графа Кауца .
Графы Кауца тесно связаны с графами де Брёйна.
Свойства
[править | править код]- Для фиксированной степени и числа вершин граф Кауца имеет наименьший диаметр для любого ориентированного графа с вершинами и степенью .
- Все графы Кауца имеют эйлеровы циклы. (Эйлеров цикл — это цикл, который посещает каждое ребро ровно раз — этот результат следует из того, что графы Кауца имеют полустепень захода равную полустепени исхода для каждого узла).
- Все графы Кауца имеют гамильтонов цикл (Этот результат следует из соответствия, описанного выше между рёбрами графа Кауца и вершинами графа Кауца . Гамильтонов цикл на задаётся эйлеровым циклом на ).
- Граф Кауца степени имеет непересекающихся пути из любого узла в любой другой узел .
В обработке данных
[править | править код]Граф Кауца использовался в качестве сетевой технологии для соединения процессоров в высокопроизводительных вычислениях[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.
Для улучшения этой статьи желательно:
|