Головна |
У 1857 році математик Вільям Роуен Гамільтон придумав гру. Існує кілька версій того, як це сталося. За однією з версій він описав гру в листі до друга. Відповідно до іншої, він дійсно винайшов гру і продав її виробнику іграшок. У будь-якому випадку, ця гра включала додекаедр, тобто правильний багатогранник, 12 граней яких представляли собою рівні правильні п'ятикутник. У кожному з 20 кутів, або вершин тіла, просвердлюють дірочка, в яку вставлявся кілочок, який зображав місто. Використовуючи мотузку, потрібно знайти шлях через міста, відвідавши кожне місто один раз, і повернутися в початковий місто.
У цьому випадку проблема зводиться до знаходження в графі циклу, що проходить через кожну вершину тільки один раз, виключаючи початкову. Звідси будь-який цикл, що володіє такою властивістю, називається Гамільтона циклом. Цей цикл в деякому сенсі протилежний ейлерову циклу, який проходить через всі ребра тільки один раз. До певного моменту обидва циклу можуть здатися схожими, але насправді цикл Гамільтона набагато складніше.
нехай - Граф.
визначення 4.4. Гамильтонов шлях - Це простий шлях, який проходить через кожну вершину графа . Гамильтонов цикл - Це простий цикл, який проходить через кожну вершину графа .
До теперішнього часу нікому не вдалося встановити необхідні і достатні умови існування у графа Гамільтона циклу. Проте доведено ряд теорем, в яких наводяться деякі умови існування у графа Гамільтона циклу.
Розглянемо одну з задач, в якій потрібно знайти у зваженому графі гамільтонів цикл мінімальної довжини. Наведемо формулювання завдання і алгоритм її вирішення.
Завдання комівояжера (або бродячого торговця)
Постановка завдання: комівояжер повинен так скласти свій маршрут руху, щоб відвідати один і тільки один раз кожен з міст і повернутися в початковий пункт. Його маршрут повинен мінімізувати сумарну довжину пройденого шляху.
Після текстової постановки задачі за допомогою математичного мови (символів, функцій, рівнянь або нерівностей і т.д.) побудуємо математичну модель задачі. Суворе поняття «математична модель» введемо в наступному розділі «Елементи математичного моделювання», на даному етапі будемо оперувати даними поняттям, як деяким математичним «перекладом» текстового умови.
Отже, нехай - Матриця відстаней між містами. Для складання математичної моделі задачі позначимо через змінні факт переїзду комівояжером з міста в місто . Оскільки переїзд з одного міста в інший може здійснюватися тільки один раз, то змінні повинні приймати тільки два значення: 1 або 0, тобто булеві значення. Таким чином:
Математична модель задачі має наступний вигляд:
(4.1)
(4.2)
(4.3)
.
Система обмежень (4.2) забезпечує побудова маршруту, при якому комівояжер в'їжджає в кожне місто тільки один раз, а система (4.3) - маршруту, при якому він виїжджає з кожного міста тільки один раз. Усунення підциклів і отримання маршруту, що утворює повний цикл, що включає всі міста, досягається при додаванні системи обмежень:
(4.4)
де всі змінні и можуть приймати довільні дійсні значення.
Подання графів в комп'ютері | Приклад 1.6. | дерева | Приклад 2.1. | остовне дерева | Приклад 2.2. | Алгоритм Краскала і алгоритм Прима | алгоритм Краскала | алгоритм Прима | алгоритм Дейкстри |