Меню
Главная
Случайная статья
Настройки
|
Граф Кауца — это ориентированный граф степени и размерности , который имеет вершин, помеченных всеми возможными строками длины , которые составлены из символов , выбранных из алфавита , содержащего различных символов с условием, что соседние символы не могут совпадать ().
Граф Кауца имеет рёбер
Естественно пометить каждое такое ребро как , создавая один-к-одному соответствие между рёбрами графа Кауца и вершинами графа Кауца .
Графы Кауца тесно связаны с графами де Брёйна.
Содержание
Свойства- Для фиксированной степени и числа вершин граф Кауца имеет наименьший диаметр для любого ориентированного графа с вершинами и степенью .
- Все графы Кауца имеют эйлеровы циклы. (Эйлеров цикл — это цикл, который посещает каждое ребро ровно раз — этот результат следует из того, что графы Кауца имеют полустепень захода равную полустепени исхода для каждого узла).
- Все графы Кауца имеют гамильтонов цикл (Этот результат следует из соответствия, описанного выше между рёбрами графа Кауца и вершинами графа Кауца . Гамильтонов цикл на задаётся эйлеровым циклом на ).
- Граф Кауца степени имеет не пересекающихся пути из любого узла в любой другой узел .
В обработке данных
Граф Кауца использовался в качестве сетевой технологии для соединения процессоров в высокопроизводительных вычислениях[1] и отказоустойчивых вычислениях[2], такие сети известны как сети Кауца.
Примечания
- Darcy, 2007.
- Li, Lu, Su, 2004, с. 308–315.
Литература
|
|