Page 110 - 4204

ЛЕКЦІЯ 8. ЗАДАЧІ МЕРЕЖЕВОГО АНАЛІЗУ З ЕЛЕМЕНТАМИ ТЕОРІЇ ГРАФІВ

Наприклад, є система шляхів, які потрібно відремонтувати. Ремон-

тна бригада повинна проїхати через усі ці шляхи, починаючи від своєї бази.

Бригада має спеціальну техніку, яка рухається дуже повільно, тому ба-

жано двічі тим самим шляхом не проїжджати. Виходить, що найкращим

маршрутом бригади буде саме ейлерів цикл, який починається й закінчу-

ється в її базі.

Подібні задачі побудови оптимальних маршрутів є актуальними

для організації механізованого чищення вулиць, прибирання сні-

гу, пасажирських перевезень і т. п.

14
8.2. Задача комівояжера

Однією з важливих мережевих задач є так звана задача ко-

мівояжера – знайти найкоротший замкнутий маршрут, що про-

ходить через усі вершин графа по одному разу (знайти найкоро-

тший гамільтонів цикл).

Цю задачу можна сформулювати ще так: нехай у місті M
0

знаходиться кур’єрська служба і кур’єр повинен розвести листи в

інші міста M , M ... , , M , відвідуючи кожне місто лише по одно-
n
2
1
му разу. Зрозуміло, що є багато різних способів об’їхати всі міс-

та. Який з маршрутів буде найкоротший?

Для знаходження відповіді при невеликих n найпростіше

проаналізувати всі варіанти (метод перебору варіантів) за допо-

могою нового графу.

14
Комівояжер (франц. commis voyageur) – торговий агент. Інша назва цієї задачі – зада-
ча листоноші.

109