3.2.5. Гамильтоновы цепи и циклы

Пусть G – псевдограф.

Определение. Цепь (цикл) в G называется гамильтоновой (гамильтоновыми), если она (он) проходит по одному разу через каждую вершину псевдографа G.

Определение. Граф является гамильтоновым, если он содержит гамильтонов цикл.

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

Приведем теорему Дирака, которая отвечает на вопрос: существует ли в графе гамильтонов цикл.

Теорема. Если в простом графе с n (? 3) вершинами локальная степень каждой вершины не менее n/2, то граф является гамильтоновым.

Пример 85.

Любой простой полный граф является гамильтоновым. Любой циклический граф является гамильтоновым. Граф, являющийся колесом, является гамильтоновым.

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 3.2.5. Гамильтоновы цепи и циклы:

  1. Кредиты такого рода погашаются по окончании операционного цикла за счет выручки от продажи активов.
  2. ряд примеров приложений теории графов.
  3. 1.8.2 Средства обеспечения освоения курса
  4. Представление логистических цепей на базе отчетности из системы MfgXPro
  5. Параметры циклов амплификации
  6. САГИ УЛАДСКОГО ЦИКЛА
  7. Эйлеровы и гамильтоновы графы.
  8. Деревья и циклы.
  9. Более чем столетние циклы
  10. 4.2. СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ
  11. §5. Графы
  12. ФАКТОРЫ СТАНОВЛЕНИЯ ОРГАНИЗМА ХОЗЯИНОМ ПАРАЗИТОВ
  13. Пути в графах
  14. Метрические характеристики графа
  15. 3.1.5. Маршруты, цепи, циклы
  16. 3.2.4. Эйлеровы цепи и циклы