Тема 8, Гамильтоновы графы

Тема 8, Гамильтоновы графы.

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




Метод ветвей и границ для решения задачи коммивояжера.
Суть идеи метода ветвей и границ состоит в следующем. Все перебираемые варианты разбиваются на классы. Для каждого класса находится оценка снизу всех решений этого класса. Если оценка превышает стоимость ранее найденного решения, все варианты класса отбрасываются.

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

Заметим, что если вычесть одно и то же число из элементов одной строки, то стоимость любого пути коммивояжера уменьшится на это число, т. к. элементы i-й строки можно интерпретировать как стоимости въезда в i-й город из остальных городов, а в любой город коммивояжер въезжает ровно один раз. Аналогичные рассуждения можно провести для столбца: вычитание одного и того же числа из элементов столбца приводит к уменьшению стоимости пути коммивояжера на это число, т. к. элементы i-го столбца можно интерпретировать как стоимости переезда из i-го города в остальные города, а из любого города коммивояжер выезжает ровно один раз.

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



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Тема 8, Гамильтоновы графы - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: графы