Тема 5 Числові методи аналізу

Багато практичних важливих задач пов'язано з термінологією гамільтонових циклів. Їх можна звести до двох типів:

1. Перерахувати всі гамільтонови цикли або контури.

2. Даний повний зважений граф (такий, що всім ребрам приписані числові характеристики – довжина, вага, вартість). Необхідно знайти гамільтонів цикл, в якому сума ваг включених ребер є мінімальною

Остання задача є так званою задачею комівояжера і може трактуватися наступними практичними задачами:

1. Є одна вантажна машина, яка повинна доставити вантажі по n різним шляхам. Довжина усіх цих шляху не залежить від порядку, в якому вони будуть обходитися. Необхідно вибрати таку послідовність маршрутів, щоб загальний час роботи машини був мінімальним.

2. Існує трубопровід. По ньому необхідно передати n різних видів нафтопродуктів, причому, значення К₁ першого нафтопроводу, К_n – останнього нафтопроводу задані і не залежать не від чого. Але втрати нафтопродуктів у наслідок їх змішування або не змішування різні, в залежності від того, в якій послідовності нафтопродукти подаються. Необхідно вибрати таку послідовність, щоб втрати були мінімальні.

В цьому випадку найбільш простим рішенням є побудова дерева прийняття рішень.

Н-граф називається неорієнтованим деревом (або просто деревом), якщо він є зв'язаним та не містить циклів, а значить, петель та кратних ребер. Дерево - це мінімальний зв'язаний граф в том сенсі, що при видаленні хоча б одного ребра він втрачає зв'язність. Існування цих двох властивостей (зв'язності та відсутність циклів) дозволяє жорстко зв'язувати число вершин та число ребер: в дереві с n вершинами завжди n-1 ребро.