Контрольна робота №3.

Завдання №1

Задано граф G. Представити граф у виді матриць суміжності й суміжності ваг. Знайти найкоротший шлях і його довжину між двома зазначеними вершинами графа (варіант із номером, який кратний 2, - методом Дейкстри, інші варіанти - методом Форда, за необхідності розставивши напрямок дуг від вершини з меншим індексом до вершини з більшим індексом). Варіанти завдань знаходяться у додатку.

Завдання №2

Орієнтований граф G=(X,U) заданий у видгляді матриці суміжності ваг С. Потрібно:

1) представити граф графічно й у видгляді матриці інциденцій;

2) визначити хроматичне число графа;

3) використовуючи метод Шимбела, визначити найкоротші відстані між будь-якими двома вершинами графа.

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

11. 12.

13. 14.

15. 16.

17. 18.

19. 20.

21. 22.

23. 24.

25. 26.

27. 28.

29. 30.

Завдання №3

У розподільній системі опрацювання даних у деякий момент часу є n ресурсів готових до виконання завдань. У систему надходить n завдань. Відома якість виконання завдань кожним ресурсом (коефіцієнти матриці С). Потрібно призначити кожному ресурсу своє завдання таким чином, щоб якість виконання всіх завдань була максимальною.

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

11. 12.

13. 14.

15. 16.

17. 18.

19. 20.

21. 22.

23. 24.

25. 26.

27. 28.

29. 30.

Завдання №4

Транспортна мережа задана за допомогою таблиці, де зазначені дуги мережі і пропускна спроможність цих дуг. Необхідно представити граф графічно і, використовуючи теорему Форда-Фалкерсона, визначити найбільший потік у мережі (s - джерело, t - стік). Перелік дуг мережі у вигляді

1. u_s1=13, u_s2=17, u_s3=1, u_1t=7, u₁₃=5, u₂₃=2, u₂₄=17, u₃₄=1, u_3t=2, u_4t=12

2. u_s1=16, u_s2=14, u₁₃=9, u₂₁=10, u₂₃=5, u₂₄=8, u₃₅=6, u_3t=9, u₄₅=1, u_4t=6, u_5t=6.

3. u_s1=6, u_s2=10, u_s3=3, u₁₂=3, u₁₄=2, u₁₃=2, u₂₄=1, u_2t=8, u₃₂=4, u₃₄=5, u_4t=9

4. u_s1=3, u_s2=5, u_s3=4, u_s4=1, u_1t=7, u₂₁=2, u₂₄=1, u_2t=1, u₃₂=3, u₃₄=2, u_4t=3

5. u_s1=25, u_s2=18, u₁₂=4, u₁₄=10, u₂₄=10, u_2t=15, u_3t=5, u₄₃=10, u_4t=10

6. u_s1=5, u_s2=4, u_s3=6, u_1t=4, u₁₄=1, u₁₃=1, u₂₃=3, u₂₄=2, u₃₄=2, u_3t=3, u_4t=7

7. u_s1=12, u_s2=20, u_s3=5, u_1t=10, u₁₃=8, u₂₃=5, u₂₄=10, u₃₄=4, u_3t=8, u_4t=12

8. u_s1=8, u_s3=4, u_s4=6, u₁₂=4, u₂₄=2, u_2t=10, u₃₁=3, u₃₂=2, u₃₄=5, u_4t=7

9. u_s1=10, u_s2=10, u_s3=15, u₁₄=7, u₁₂=4, u₂₄=6, u₃₂=5, u_3t=20, u_4t=10

10. u_s1=6, u_s2=7, u_s3=5, u₁₂=3, u₁₄=2, u₁₃=1, u₂₃=4, u₂₄=2, u_2t=3, u_3t=7, u_4t=8

11. u_s1=5, u_s2=6, u_s3=8, u₁₂=2, u₁₄=3, u₁₃=1, u₂₄=1, u_2t=4, u_3t=5, u_4t=6

12. u_s1=10, u_s2=3, u_s3=15, u_1t=5, u₁₂=8, u₂₃=16, u₂₄=4, u_2t=15, u₃₄=5, u_4t=20

13. u_s1=7, u_s4=15, u_st=5, u_1t=3, u₁₃=5, u₂₁=10, u₃₄=3, u₄₂=20, u_4t=6

14. u_s1=20, u_s4=5, u₁₂=17, u₁₃=6, u₂₄=10, u_2t=3, u₃₂=10, u_3t=5, u_4t=20

15. u_s1=25, u_s3=40, u₁₄=20, u₁₃=15, u_2t=40, u₃₂=20, u_3t=15, u_4t=7

16. u_s1=6, u_s2=14, u_1t=10, u₁₄=3, u₂₃=3, u₂₁=10, u₂₄=2, u₃₄=5, u_4t=8

17. u_s1=5, u_s2=18, u_s5=7, u₁₄=15, u₂₃=25, u₃₅=10, u_3t=4, u₄₃=10, u_4t=10, u_5t=2

18. u_s1=20, u_s2=10, u_s3=15, u₁₂=15, u₂₃=20, u₂₅=15,u₃₄=4,u₃₅=8, u_3t=1,u_4t=20,u_5t=4

19. u_s1=10, u_s2=5, u_s4=10, u₁₂=1, u₁₃=5, u₁₄=8, u₃₄=4, u_3t=4, u₄₂=5, u_2t=20

20. u_s1=15, u_s2=20, u_s3=5, u_1t=15, u₁₂=8, u₂₃=16, u₂₄=4, u_2t=10, u₃₄=5, u_4t=3

21. u_s1=10, u_s3=15, u₁₄=8, u_1t=13, u₂₄=15, u₃₁=6, u₃₂=3, u_3t=5, u_4t=12

22. u_s3=10, u_s4=15, u_1t=13, u_2t=20, u₃₁=8, u₃₄=5, u₄₁=2, u₄₂=8, u_4t=12

23. u_s1=15, u_s2=12, u_s3=11, u_1t=9, u₁₄=7, u₁₃=6, u₂₃=7, u₂₁=10, u₃₄=8, u_3t=8, u_4t=17

24. u_s1=13, u_s2=17, u_s3=1, u_1t=7, u₁₃=5, u₂₃=2, u₂₄=17, u₃₄=1, u_3t=2, u_4t=12

25. u_s1=9, u_s2=7, u_s3=10, u_s4=12, u₁₃=6, u₁₄=8, u₂₃=6, u₂₄=6, u_3t=14, u₄₃=8, u_4t=10

26. u_s1=8, u_s2=7, u_s4=16, u_1t=7, u₁₂=5, u₂₃=10, u_3t=12, u₄₃=6, u₄₅=10, u₅₃=7, u_5t=9

27. u_s1=11, u_s2=19, u_1t=15, u₁₄=8, u₂₃=8, u₂₁=15, u₂₄=7, u₃₄=10, u_4t=13, u_2t=2

28. u_s1=10, u_s2=3, u_s3=15, u_1t=5, u₁₂=8, u₂₃=16, u₂₄=4, u_2t=15, u₃₄=5, u_4t=20

29. u_s1=5, u_s2=18, u_s5=7, u₁₄=15, u₂₃=25, u₃₅=10, u_3t=4, u₄₃=10, u_4t=10, u_5t=2

30. u_s1=25, u_s2=18, u₁₂=4, u₁₄=10, u₂₄=10, u_2t=15, u_3t=5, u₄₃=10, u_4t=10

31. u_s1=6, u_s2=10, u_s3=3, u₁₂=3, u₁₄=2, u₁₃=2, u₂₄=1, u_2t=8, u₃₂=4, u₃₄=5, u_4t=9