Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Teoria_igr_i_issled_operatsy.doc
Скачиваний:
170
Добавлен:
07.06.2015
Размер:
5.21 Mб
Скачать

Самостоятельная работа 17.

Для графа, имеющего вид

найти:

    1. максимальный поток, который может быть пропущен и вершины 1 в вершину 9,

    2. разрез, на котором максимальный поток равен его пропускной способности,

    3. найти разрез, на котором максимальный поток меньше его пропускной способности.

Варианты заданий приведены в следующей таблице:

Номер

v1

v2

v3

v4

v5

v6

v7

v8

v9

v10

v11

v12

v13

v14

v15

v16

v17

1

7

12

12

2

5

7

7

5

2

2

4

6

7

6

3

2

3

2

4

12

11

5

7

7

5

2

2

4

6

7

6

3

2

3

6

3

12

9

7

7

7

5

2

2

4

6

7

6

3

2

3

6

7

4

11

9

8

7

5

2

2

4

6

7

6

3

2

3

6

7

6

5

10

10

10

5

2

2

4

6

7

6

3

2

3

6

7

6

4

6

12

13

9

7

6

3

2

3

6

7

6

4

2

2

5

7

7

7

14

7

7

6

3

2

3

6

7

6

4

2

2

5

7

7

4

8

9

9

11

3

2

3

6

7

6

4

2

2

5

7

7

4

2

9

9

10

13

2

3

6

7

6

4

2

2

5

7

7

4

2

2

10

9

13

9

3

6

7

6

4

2

2

5

7

7

4

2

2

4

11

6

11

12

2

5

7

7

4

2

2

4

7

7

5

2

2

3

12

4

12

11

5

7

7

4

2

2

4

7

7

5

2

2

3

6

13

10

11

6

9

7

4

2

2

4

7

7

5

2

2

3

6

7

14

12

9

7

7

4

2

2

4

7

7

5

2

2

3

6

7

6

5

8

12

8

2

4

7

7

5

2

2

3

6

7

6

3

2

3

16

12

7

9

7

7

4

2

2

5

7

7

5

2

2

4

6

7

17

13

7

8

7

4

2

2

5

7

7

5

2

2

4

6

7

6

18

12

9

9

4

2

2

5

7

7

5

2

2

4

6

7

6

3

19

7

8

14

2

2

5

7

7

5

2

2

4

6

7

6

3

2

20

7

7

15

2

2

4

6

7

6

3

2

3

6

7

6

4

2

21

7

9

12

2

4

6

7

6

3

2

3

6

7

6

4

2

2

22

5

12

12

4

6

7

6

3

2

3

6

7

6

4

2

2

5

23

12

11

4

6

7

6

3

2

3

6

7

6

4

2

2

5

7

24

12

11

5

7

7

6

4

2

2

5

7

7

4

2

2

4

7

25

12

10

6

7

6

4

2

2

5

7

7

4

2

2

4

7

7

26

11

8

11

6

4

2

2

5

7

7

4

2

2

4

7

7

5

27

9

11

9

4

2

2

5

7

7

4

2

2

4

7

7

5

2

28

7

12

9

2

2

5

7

7

4

2

2

4

7

7

5

2

2

29

11

9

9

4

2

2

4

7

7

5

2

2

3

6

7

6

3

30

11

9

9

2

2

4

7

7

5

2

2

3

6

7

6

3

2

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]