Меню

Главная
Случайная статья
Настройки
Граф Кауца
Материал из https://ru.wikipedia.org

Граф Кауца  — это ориентированный граф степени и размерности , который имеет вершин, помеченных всеми возможными строками длины , которые составлены из символов , выбранных из алфавита , содержащего различных символов с условием, что соседние символы не могут совпадать ().

Граф Кауца имеет рёбер



Естественно пометить каждое такое ребро как , создавая один-к-одному соответствие между рёбрами графа Кауца и вершинами графа Кауца .

Графы Кауца тесно связаны с графами де Брёйна.

Содержание

Свойства
  • Для фиксированной степени и числа вершин граф Кауца имеет наименьший диаметр для любого ориентированного графа с вершинами и степенью .
  • Все графы Кауца имеют эйлеровы циклы. (Эйлеров цикл — это цикл, который посещает каждое ребро ровно раз — этот результат следует из того, что графы Кауца имеют полустепень захода равную полустепени исхода для каждого узла).
  • Все графы Кауца имеют гамильтонов цикл (Этот результат следует из соответствия, описанного выше между рёбрами графа Кауца и вершинами графа Кауца . Гамильтонов цикл на задаётся эйлеровым циклом на ).
  • Граф Кауца степени имеет не пересекающихся пути из любого узла в любой другой узел .


В обработке данных

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

Примечания
  1. Darcy, 2007.
  2. Li, Lu, Su, 2004, с. 308–315.


Литература
Downgrade Counter