Решение задач оптимизации с помощью графов

[Список тем] [Вступление] Страницы практической работы: [1] [2]

Практическая работа № 9

Решение задач оптимизации с помощью графов

Цель работы:

Приобрести навыки использования алгоритмов поиска кратчайшего пути, максимального
потока в сети, минимального покрывающего дерева.

Задание

Дана сеть:

Найти максимальный поток в сети от s к t, если N - номер варианта

Дана сеть:

Найти минимальный путь в сети от s к t, если N - номер варианта

Построить минимальное покрывающее дерево и определить его вес, если известны расстояния между вершинами.

1 вариант 2 вариант 3 вариант 4 вариант

b c d e f

3 4 18 15 16 a

5 13 11 14 b

20 12 19 c

8 10 d

9 e

b c d e f

6 7 16 17 13 a

10 18 15 19 b

20 21 22 c

11 9 d

8 e

b c d e f

9 10 11 22 17 a

8 21 18 23 b

19 16 20 c

12 15 d

13 e

b c d e f

5 3 18 15 16 a

4 13 11 14 b

20 12 19 c

10 9 d

8 e

5 вариант 6 вариант 7 вариант 8 вариант

b c d e f

5 6 18 15 16 a

7 13 11 14 b

20 12 19 c

8 10 d

11 e

b c d e f

8 9 16 17 13 a

12 18 15 19 b

20 21 22 c

13 11 d

10 e

b c d e f

7 9 11 22 17 a

8 21 18 23 b

19 16 20 c

13 15 d

12 e

b c d e f

8 5 18 15 16 a

6 13 11 14 b

20 12 19 c

10 9 d

7 e

9 вариант 10 вариант 11 вариант 12 вариант

b c d e f

5 3 18 15 16 a

4 13 11 14 b

20 12 19 c

11 9 d

8 e

b c d e f

10 6 16 17 13 a

7 18 15 19 b

20 21 22 c

9 8 d

11 e

b c d e f

8 9 11 22 17 a

10 21 18 23 b

19 16 20 c

15 13 d

14 e

b c d e f

4 5 18 15 16 a

6 13 11 14 b

20 12 19 c

8 10 d

9 e

13 вариант 14 вариант 15 вариант 16 вариант

b c d e f

2 3 18 15 16 a

5 13 11 14 b

20 12 19 c

6 10 d

9 e

b c d e f

4 5 16 17 13 a

10 18 15 19 b

20 21 22 c

11 9 d

7 e

b c d e f

7 9 11 22 17 a

8 21 18 23 b

19 16 20 c

11 14 d

13 e

b c d e f

4 2 18 15 16 a

3 13 11 14 b

20 12 19 c

10 8 d

7 e

17 вариант 18 вариант 19 вариант 20 вариант

b c d e f

3 4 18 15 16 a

5 13 11 14 b

20 12 19 c

8 10 d

9 e

b c d e f

6 7 16 17 13 a

10 18 15 19 b

20 21 22 c

11 9 d

8 e

b c d e f

9 10 11 22 17 a

8 21 18 23 b

19 16 20 c

12 15 d

13 e

b c d e f

5 3 18 15 16 a

4 13 11 14 b

20 12 19 c

10 9 d

8 e

21 вариант 22 вариант 23 вариант 24 вариант

b c d e f

5 6 18 15 16 a

7 13 11 14 b

20 12 19 c

8 10 d

11 e

b c d e f

8 9 16 17 13 a

12 18 15 19 b

20 21 22 c

13 11 d

10 e

b c d e f

7 9 11 22 17 a

8 21 18 23 b

19 16 20 c

13 15 d

12 e

b c d e f

8 5 18 15 16 a

6 13 11 14 b

20 12 19 c

10 9 d

7 e

25 вариант 26 вариант 27 вариант 28 вариант

b c d e f

5 3 18 15 16 a

4 13 11 14 b

20 12 19 c

11 9 d

8 e

b c d e f

10 6 16 17 13 a

7 18 15 19 b

20 21 22 c

9 8 d

11 e

b c d e f

8 9 11 22 17 a

10 21 18 23 b

19 16 20 c

15 13 d

14 e

b c d e f

4 5 18 15 16 a

6 13 11 14 b

20 12 19 c

8 10 d

9 e

29 вариант 30 вариант 31 вариант 32 вариант

b c d e f

2 3 18 15 16 a

5 13 11 14 b

20 12 19 c

6 10 d

9 e

b c d e f

4 5 16 17 13 a

10 18 15 19 b

20 21 22 c

11 9 d

7 e

b c d e f

7 9 11 22 17 a

8 21 18 23 b

19 16 20 c

11 14 d

13 e

b c d e f

4 2 18 15 16 a

3 13 11 14 b

20 12 19 c

10 8 d

7 e

[Список тем] [Вступление] Страницы практической работы: [1] [2]