Гамильтоновы графы. Постановка задачи коммивояжера

Граф называется гамильтоновым, если в нем имеется простой цикл (гамильтонов цикл), содержащий каждую вершину этого графа. Простая цепь, содержащая все вершины графа, также называется гамильтоновой.

Пусть G – связный неорграф без петель, имеющий n≥3 вершин.

Достаточные условия существования гамильтоновых циклов:

1) Если для любых двух различных несмежных вершин a и b графа G выполняется условие dega+degb≥n, то существует гамильтонов цикл.

2) Если для любой вершины a графа G выполнено условие dega≥n/2, то существует гамильтонов цикл.

Задача коммивояжера:

Район, который должен посетить бродячий торговец, содержит некоторое количество городов, расстояния между которыми известны. Требуется найти кратчайший маршрут, проходящий через все пункты по одному разу и возвращающийся в исходный город.