Задать вопрос юристу

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

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

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

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

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

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

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

Пример 85.

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

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

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

  1. 3.2.4. Эйлеровы цепи и циклы
  2. 3.1.5. Маршруты, цепи, циклы
  3. Эйлеровы и гамильтоновы графы.
  4. 69. Циклы развития мирового хозяйства
  5. Внутренние циклы.
  6. 4.3.1. Информационные цепи с памятью
  7. Интегрированные гостиничные цепи.
  8. Пассионарные циклы и этногенез
  9. 19. Макроэкономическое неравновесие: экономические циклы, безработица, инфляция.
  10. § 2.6. РЕЗИСТОР В ЦЕПИ ПЕРЕМЕННОГО ТОКА
  11. §2.14. ЗАКОН ОМА ДЛЯ ПОЛНОЙ ЦЕПИ
  12. 2.2. Марковские цепи
  13. § 2.7. КОНДЕНСАТОР В ЦЕПИ ПЕРЕМЕННОГО ТОКА
  14. §2.10. МОЩНОСТЬ В ЦЕПИ ПЕРЕМЕННОГО ТОКА
  15. Более чем столетние циклы
  16. Цепи Маркова.