міжності заданого графа В
Малюнок 2.2 - Матриця ваг заданого графа
Рішення
Щоб знайти класи порядку, скористаємося алгоритмом Демукрона. Знизу від матриці суміжності приписуємо масив M, елементи якого виходять підсумовуванням елементів у стовпцях і є полустепені заходу для вершин. Перші чотири елементи масиву дорівнюють нулю, тому вершини 1, 2, 3 та 4 відносимо до першого рівня, а замість нулів у масиві пишемо *. Далі в матриці суміжності складаємо перші чотири рядки і їх суму віднімаємо з масиву М. Потім в отриманому масиві знову шукаємо нульові елементи і так повторюємо всю процедуру, поки не отримаємо масив, що повністю складається з *. Усі перетворення масиву до одержання необхідного представлені на малюнку 2.3. У результаті обчислень отримали наступні класи порядку:
N0 = {1, 2, 3, 4};
N1 = {5, 6, 7, 8};
N2 = {9, 10, 11, 13};
N3 = {12, 14, 15}; 4 = {16, 17}; 5 = {18}.
В
Малюнок 2.3 - Знаходження класів порядку
Для знаходження шляхів максимального і мінімального ваги проаналізуємо всі можливі шляхи.
З вершини 1, що належить нульового рівня, до вершини 18, що належить п'ятого рівня, ведуть шляхи: 1, 16, 18; 1, 5, 10, 14, 16, 18; 1, 5, 10, 14, 17, 18; 1, 5, 13, 16, 18; 1, 5, 13, 14, 16, 18; 1, 5, 13, 14, 17, 18; 1, 5, 13, 17, 18; 1, 5, 13, 15, 18; 1, 5, 16, 18; 1, 5, 14, 16, 18; 1, 5, 14, 17, 18; 1, 5, 18; 1, 5, 15, 18. Їх ваги: ​​6, 33, 36, 19, 32, 35, 26, 36, 5, 23, 26, 4, 22. p> З вершини 2, що належить нульового рівня, до вершини 18, що належить п'ятого рівня, ведуть шляхи: 2, 7, 12, 18; 2, 7, 17, 18; 2, 10, 14, 16, 18; 2, 10, 14, 17, 18; 2, 12, 18; 2, 14, 16, 18; 2, 14, 17, 18; 2, 17, 18; 2, 15, 18; 2, 5, 10, 14, 16, 18; 2, 5, 10, 14, 17, 18; 2, 5, 13, 16, 18; 2, 5, 13, 17, 18; 2, 5, 13, 14, 16, 18; 2, 5, 13, 14, 17, 18; 2, 5, 13, 15, 18; 2, 5, 16, 18; 2, 5, 14, 16, 18; 2, 5, 14, 17, 18; 2, 5, 18; 2, 5, 15, 18. Їх ваги: ​​29, 28, 18, 21, 15, 26, 29, 13, 17, 42, 45, 28, 35, 41, 44, 45, 14, 32, 35, 13, 31. p> З вершини 3, що належить нульового рівня, до вершини 18, що належить п'ятого рівня, ведуть шляхи: 3, 6, 16, 18; 3, 6, 17, 18; 3, 6, 11, 12, 18; 3, 6, 9, 17, 18; 3, 5, 10, 14, 16, 18; 3, 5, 10, 14, 17, 18; 3, 5, 13, 16, 18; 3, 5, 13, 14, 16, 18; 3, 5, 13, 14, 17, 18; 3, 5, 13, 17, 18; 3, 5, 13, 15, 18; 3, 5, 16, 18; 3, 5, 14, 16, 18; 3, 5, 14, 17, 18; 3, 5, 18; 3, 5, 15, 18. Їх ваги: ​​9, 13, 34, 23, 33, 36, 19, 32, 35, 26, 36, 5, 23, 26, 4, 22. p> З вершини 4, що належить нульового рівня, до вершини 18, що належить п'ятого рівня, ведуть шляхи: 4, 16, 18; 4, 17, 18; 4, 8, 11, 12, 18; 4, 8, 15, 18; 4, 8, 9, 17, 18; 4, 9, 17, 18. Їх ваги: ​​15, 7, 33, 37, 17, 15. p> Оптимальний шлях, що відповідає максимальному загального вазі 45 - 2, 5, 13, 15, 18. Оптимальні шляхи, що відповідають мінімального спільного вазі 4 - 1, 5, 18; 3, 5, 18. p> Зобразимо граф, розташувавши його вершини...
