граф має цикл, що містить всі ребра графа по одному разу, то такий цикл називається ейлеровим циклом, а граф називається ейлеровим графом. Якщо граф має ланцюг, що містить всі вершини по одному разу, то такий ланцюг називається ейлеровой ланцюгом, а граф називається полуейлеровим графом
Ясно, що Ейлером цикл містить не тільки всі ребра по одному разу, а й всі вершини графа (можливо по кілька разів). Очевидно так само, що ейлеровим може бути тільки пов'язаний граф
. Знаходження туру
Для знаходження туру, необхідно скласти суми всіх ребер з 1-го по n-ий. Отримана сума є довгою туру
. 2 Приклад
Приклад 1. Дана повна мережу, показана на малюнку 9. Знайти тур дерев'яним алгоритмом.
Малюнок 9.
Таблиця 1.
N1234561064871426071171034704310481140511577350761410101170
Малюнок 10.
Рішення:
Дерев'яний алгоритм спочатку будує остовное дерево, показане на малюнку 10 штриховою лінією, потім Ейлером цикл 1-2-1-3-4-3-5-6-5-3-1, потім тур 1-2-3-4-5-6-1 довжиною 43, який показаний суцільною лінією на малюнку 10
. 3 Рішення задач засобами Excel
Рішення завдання за допомогою надбудови MS Excel «Пошук рішення»
Програма Пошук рішень - додаткова надбудова табличного процесора MS Excel, яка призначена для вирішення певних систем рівнянь, лінійних і нелінійних задач оптимізації
За допомогою цієї надбудови можна визначити, при яких значеннях зазначених впливають осередків формула в цільовій комірці приймає потрібне значення (мінімальне, максимальне або рівну якоїсь величиною). Для процедури пошуку рішення можна задати обмеження, причому не обов'язково, щоб при цьому використовувалися ті ж впливають осередки, дані яких, визначають значення цільової осередки. Для розрахунку заданого значення застосовуються різні математичні методи пошуку. Ви можете встановити режим, в якому отримані значення змінних автоматично заносяться в таблицю. Крім того, результати роботи програми можуть бути оформлені у вигляді звіту.
Відстані між містами задані наступній матрицею:
Таблиця 2. Відстані між містами
N12345106386260265332074486709565490
Малюнок 11. Вихідні дані задачі
Вводимо формули:
Таблиця 3. Формули
ЯчейкаФормулаПрімечаніеB9=СУММ (B4: B8) Поширюємо на діапазон B9: F9G4=СУММ (B4: F4) Поширюємо на діапазон G4: G8B19=СУММПРОИЗВ (B4: F8; B13: F17) Цільова функціяE19=B4 + C5 + D6 + E7 + F8Ісключеніе шляху
Додаємо обмеження у вікно «Пошук рішень»
Малюнок 12. Вікно «Пошук рішень»
Малюнок 13. Вікно «Параметри пошуку рішень»
Малюнок 14. Результат розв'язання задачі
Висновок
У ході аналізу отриманих результатів, приходимо до висновку, що наш шлях:
- 3-2-5-4-1
Відстань=27
. Алгоритм рішення задачі
. 1 Алгоритм основної програми - Derevo
. 2 Алгоритм підпрограми - Derevalgor
