Приклад виконання роботи

Розглянемо приклад виконання роботи для схеми маршрутної мережі, наведеної на рисунку 9.2.

Спочатку перевіряємо наявність у мережі вершин з непарними степенями. Таких вершин на мережі шість: , , , , та .

Використовуючи алгоритм Дейкстри знаходимо найкоротші відстані та шляхи між всіма парами вершин з непарними степенями. В результаті отримуємо матрицю (таблиця 9.2). По діагоналі цієї матриці проставляємо знаки безкінечності.

У таблиці 9.3 наведені найкоротші шляхи, які відповідають знайденим найкоротшим відстаням.

Рисунок 9.2 — Схема мережі вулиць (приклад)

Таблиця 9.2 — Матриця найкоротших відстаней між вершинами з непарними степенями

Таблиця 9.3 — Матриця найкоротших шляхів між вершинами з непарними степенями

		2-3	2-4	2-4-6	2-3-7	2-1-8
	3-2		3-4	3-7-6	3-7	3-2-1-8
	4-2	4-3		4-6	4-6-7	4-5-8
	6-4-2	6-7-3	6-4		6-7	6-9-8
	7-3-2	7-3	7-6-4	7-6		7-6-9-8
	8-1-2	8-1-2-3	8-5-4	8-9-6	8-9-6-7

Розглянемо всі можливі паросполучення непарних вершин та підрахуємо їх сумарну довжину:

1) (2, 3); (4, 6); (7, 8): 5+10+14 = 29 км;

2) (2, 3); (4, 7); (6, 8): 5+14+10 = 29 км;

3) (2, 3); (4, 8); (6, 7): 5+13+ 4 = 22 км;

4) (2, 4); (3, 6); (7, 8): 3+13+14 = 30 км;

5) (2, 4); (3, 7); (6, 8): 3+ 9+ 10 = 22 км;

6) (2, 4): (3, 8); (6, 7): 3+18+ 4 = 25 км;

7) (2, 6); (3, 4); (7, 8): 13+7+14 = 34 км;

8) (2, 6); (4, 7); (3, 8): 13+14+18 = 45 км;

9) (2, 6); (4, 8); (3, 7): 13+13+9 = 35 км;

10) (2, 7); (4, 6); (3, 8): 14+10+18 = 42 км;

11) (2, 7); (3, 4); (6, 8): 14+7+10 = 31 км;

12) (2, 7); (4, 8); (3, 6): 14+13+13 = 40 км;

13) (2, 8); (4, 6); (3, 7): 13+10+9 = 32 км;

14) (2, 8); (4, 7); (3, 6): 13+14+13 = 40 км;

15) (2, 8); (3, 4); (6, 7): 13+7+4 = 24 км.

Таким чином, маємо два паросполучення з мінімальною довжиною (3 та 5, позначені напівжирним шрифтом). Візьмемо, наприклад, паросполучення (2, 3); (4, 8); (6, 7). У відповідності до таблиці найкоротших шляхів 9.3 додаємо до вихідного графа додаткові ребра, які відповідають найкоротшим шляхам отриманого мінімального паросполучення (показані пунктирними лініями). Отриманий після цієї операції вихідний граф наведено на рисунку 9.3.

Тепер ми маємо ейлерів граф, тобто граф, всі степені вершин якого є парними. Використовуючи алгоритм Фльорі знаходимо у ньому ейлерів цикл, починаючи, наприклад, з вершини 1:

1 - 8 - 9 - 10 - 7 - 6 - 9 - 5 - 8 - 5 - 4 - 6 - 7 - 3 - 4 - 5 - 1 - 2 - 3 - 2 - 4 - 1

Довжина цього маршруту дорівнює сумі довжин всіх ланок мережі 115 км та суми довжин доданих ребер з найменшого паросполучення (22), тобто 115+22 = 137 км.

Рисунок 9.3 — Вихідний граф, розширений фіктивними ребрами

Контрольні запитання

1. Дайте визначення ейлеревого циклу у графі.

2. У якому випадку граф називають ейлеревим? півейлеревим?

2. За яких умов у графі існує ейлерів цикл?

3. Дайте формулювання задачі листоноші.

4. Наведіть алгоритм Фльорі для побудови ейлерева циклу у ейлеревому графі.

5. Що таке найменше паросполучення у графі і як воно відшукується?

САМОСТІЙНА РОБОТА №10

ОПТИМІЗАЦІЯ МЕРЕЖЕВИХ ГРАФІКІВ

ЗА ЧАСОМ І РЕСУРСАМИ

Мета роботи: вивчення методів розподілу обмежених ресурсів з метою виконання комплексу робіт, заданих мережевою моделлю, у найкоротший термін послідовним та паралельним методами.

Стисла теоретична довідка

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

При виконанні реальних проектів ресурси, як правило, обмежені, внаслідок чого на послідовність виконання робіт накладаються додаткові обмеження, пов’язані з наявністю вільних ресурсів у даний момент часу.

Процедура розподілу ресурсів полягає в плануванні початку виконання робіт у відповідності з умовами слідування та наявності вільних ресурсів. Для реалізації цієї процедури існують декілька методів, до яких відносяться послідовний та паралельний.

Послідовний метод.