3.2.5. Гамильтоновы цепи и циклы
Пусть G – псевдограф.
Определение. Цепь (цикл) в G называется гамильтоновой (гамильтоновыми), если она (он) проходит по одному разу через каждую вершину псевдографа G.
Определение.
Граф является гамильтоновым, если он содержит гамильтонов цикл.С понятием гамильтоновых циклов тесно связана так называемая задача коммивояжера: в нагруженном графе G определить гамильтонов цикл минимальной длины (иными словами, коммерсант должен совершить поездку по городам и вернуться обратно, побывав в каждом городе ровно один раз, и при этом стоимость такой поездки должна быть минимальной).
Приведем теорему Дирака, которая отвечает на вопрос: существует ли в графе гамильтонов цикл.
Теорема. Если в простом графе с n (? 3) вершинами локальная степень каждой вершины не менее n/2, то граф является гамильтоновым.
Пример 85.
Любой простой полный граф является гамильтоновым. Любой циклический граф является гамильтоновым. Граф, являющийся колесом, является гамильтоновым.