Задания для самостоятельной работы

1. У становите, являются ли указанные графы изоморфными?

1.1.

1.2.

1 .3.

1 .4.

1 .5.

1 .6.

1.7.

1 .8.

1 .9.

1 .10.

2. Для данного графа найти максимальное количество геодезических цепей, соединяющих вершины 1, 25 и разделяющее множество, содержащее минимальное количество вершин.

2.1.

2.2.

2.3.

2.4.

2.5.

2 .6.

2 .7.

2 .8.

2 .9.

2 .10.

3. Для данного графа составить матрицу смежности, матрицу инцидентности. Провести поиски в глубину и в ширину.

3 .1.

3.2.

3 .3.

3.4.

3 .5.

3 .6.

3.7.

3.8.

3 .9.

3 .10.

4. Для заданного графа составить остовый подграф наименьшего веса с помощью алгоритма Краскала.

2 a₈ 6 a₂₁ 16 a₄₀

a₁ a₅ a₉ a₁₇ a₂₂ 12 a₂₇ a₃₈ 19

a₂ 3 a₁₀ a₂₃ a₂₈ a₂₉ a₄₁ a₄₃

1 a₃ a₆ a₁₁ 7 13 a₃₀ 17 a₄₂

a₄ 4 a₁₂ a₁₈ a₂₄ a₃₁ a₃₂ a₃₃ a₄₄ a₄₈ 23

a₇ 9 a₂₅ 20 a₄₉

5 a₁₃ 8 a₁₄ a₁₉ 14 a₃₄ 18 a₄₆ a₄₅ 22

a₁₅ a₁₆ 10 a₂₆ a₃₅ a₃₆ 21 a₄₇

11 a₂₀ 15 a₃₇

4.1. a₁=1, a₂=2, a₃=4, a₄=3, a₅=6, a₆=2, a₇=7, a₈=1, a₉=4, a₁₀=6, a₁₁=8, a₁₂=3, a₁₃=7, a₁₄=4, a₁₅=2, a₁₆=2, a₁₇=4, a₁₈=3, a₁₉=6, a₂₀=2, a₂₁=7, a₂₂=1, a₂₃=4, a₂₄=6, a₂₅=8, a₂₆=3, a₂₇=7, a₂₈=2, a₂₉=2, a₃₀=4, a₃₁=3, a₃₂=6, a₃₃=2, a₃₄=7, a₃₅=1, a₃₆=4, a₃₇=6, a₃₈=8, a₃₉=3, a₄₀=7, a₄₁=4, a₄₂=2, a₄₃=2, a₄₄=4, a₄₅=3, a₄₆=6, a₄₇=2, a₄₈=7, a₄₉=1.

4.2. a₁=2, a₂=2, a₃=4, a₄=3, a₅=5, a₆=2, a₇=7, a₈=5, a₉=4, a₁₀=6, a₁₁=1, a₁₂=3, a₁₃=7, a₁₄=4, a₁₅=2, a₁₆=2, a₁₇=4, a₁₈=3, a₁₉=5, a₂₀=1, a₂₁=7, a₂₂=5, a₂₃=4, a₂₄=3, a₂₅=8, a₂₆=1, a₂₇=7, a₂₈=4, a₂₉=2, a₃₀=4, a₃₁=3, a₃₂=8, a₃₃=2, a₃₄=7, a₃₅=1, a₃₆=4, a₃₇=6, a₃₈=9, a₃₉=3, a₄₀=7, a₄₁=4, a₄₂=4, a₄₃=2, a₄₄=4, a₄₅=3, a₄₆=6, a₄₇=5, a₄₈=7, a₄₉=2.

4.3. a₁=3, a₂=2, a₃=4, a₄=3, a₅=7, a₆=2, a₇=7, a₈=1, a₉=4, a₁₀=6, a₁₁=8, a₁₂=3, a₁₃=7, a₁₄=4, a₁₅=5, a₁₆=2, a₁₇=4, a₁₈=5, a₁₉=6, a₂₀=2, a₂₁=7, a₂₂=1, a₂₃=4, a₂₄=8, a₂₅=8, a₂₆=3, a₂₇=6, a₂₈=2, a₂₉=2, a₃₀=4, a₃₁=4, a₃₂=6, a₃₃=2, a₃₄=7, a₃₅=1, a₃₆=4, a₃₇=6, a₃₈=2, a₃₉=3, a₄₀=7, a₄₁=4, a₄₂=1, a₄₃=2, a₄₄=4, a₄₅=3, a₄₆=6, a₄₇=5, a₄₈=7, a₄₉=1.

4.4. a₁=4, a₂=2, a₃=4, a₄=1, a₅=6, a₆=2, a₇=7, a₈=1, a₉=4, a₁₀=6, a₁₁=9, a₁₂=3, a₁₃=7, a₁₄=4, a₁₅=2, a₁₆=6, a₁₇=4, a₁₈=3, a₁₉=6, a₂₀=2, a₂₁=7, a₂₂=1, a₂₃=6, a₂₄=6, a₂₅=2, a₂₆=3, a₂₇=7, a₂₈=2, a₂₉=9, a₃₀=4, a₃₁=3, a₃₂=6, a₃₃=2, a₃₄=7, a₃₅=5, a₃₆=4, a₃₇=6, a₃₈=8, a₃₉=3, a₄₀=3, a₄₁=4, a₄₂=2, a₄₃=2, a₄₄=5, a₄₅=3, a₄₆=6, a₄₇=6, a₄₈=7, a₄₉=5.

4.5. a₁=5, a₂=3, a₃=4, a₄=1, a₅=6, a₆=2, a₇=5, a₈=1, a₉=4, a₁₀=6, a₁₁=9, a₁₂=3, a₁₃=7, a₁₄=4, a₁₅=2, a₁₆=7, a₁₇=1, a₁₈=3, a₁₉=6, a₂₀=2, a₂₁=7, a₂₂=1, a₂₃=6, a₂₄=6, a₂₅=4, a₂₆=3, a₂₇=7, a₂₈=2, a₂₉=9, a₃₀=5, a₃₁=8, a₃₂=6, a₃₃=2, a₃₄=7, a₃₅=5, a₃₆=4, a₃₇=6, a₃₈=8, a₃₉=3, a₄₀=3, a₄₁=2, a₄₂=4, a₄₃=2, a₄₄=5, a₄₅=3, a₄₆=6, a₄₇=6, a₄₈=7, a₄₉=6.

4.6. a₁=6, a₂=5, a₃=4, a₄=3, a₅=6, a₆=2, a₇=7, a₈=1, a₉=4, a₁₀=6, a₁₁=9, a₁₂=3, a₁₃=7, a₁₄=4, a₁₅=2, a₁₆=6, a₁₇=5, a₁₈=4, a₁₉=6, a₂₀=2, a₂₁=6, a₂₂=8, a₂₃=6, a₂₄=6, a₂₅=2, a₂₆=3, a₂₇=7, a₂₈=2, a₂₉=9, a₃₀=7, a₃₁=2, a₃₂=7, a₃₃=2, a₃₄=1, a₃₅=5, a₃₆=4, a₃₇=6, a₃₈=8, a₃₉=3, a₄₀=3, a₄₁=4, a₄₂=2, a₄₃=6, a₄₄=4, a₄₅=3, a₄₆=6, a₄₇=2, a₄₈=7, a₄₉=7.

4.7. a₁=7, a₂=3, a₃=4, a₄=1, a₅=6, a₆=2, a₇=7, a₈=7, a₉=4, a₁₀=6, a₁₁=9, a₁₂=3, a₁₃=7, a₁₄=4, a₁₅=5, a₁₆=2, a₁₇=4, a₁₈=1, a₁₉=5, a₂₀=2, a₂₁=5, a₂₂=8, a₂₃=6, a₂₄=6, a₂₅=2, a₂₆=3, a₂₇=7, a₂₈=1, a₂₉=6, a₃₀=4, a₃₁=3, a₃₂=6, a₃₃=3, a₃₄=7, a₃₅=5, a₃₆=4, a₃₇=6, a₃₈=8, a₃₉=3, a₄₀=3, a₄₁=4, a₄₂=7, a₄₃=4, a₄₄=8, a₄₅=1, a₄₆=6, a₄₇=6, a₄₈=7, a₄₉=8.

4.8. a₁=8, a₂=5, a₃=4, a₄=1, a₅=7, a₆=2, a₇=7, a₈=1, a₉=4, a₁₀=6, a₁₁=9, a₁₂=3, a₁₃=7, a₁₄=4, a₁₅=2, a₁₆=7, a₁₇=8, a₁₈=3, a₁₉=6, a₂₀=2, a₂₁=7, a₂₂=1, a₂₃=6, a₂₄=6, a₂₅=2, a₂₆=3, a₂₇=7, a₂₈=3, a₂₉=4, a₃₀=4, a₃₁=3, a₃₂=6, a₃₃=2, a₃₄=7, a₃₅=5, a₃₆=4, a₃₇=6, a₃₈=8, a₃₉=3, a₄₀=7, a₄₁=2, a₄₂=2, a₄₃=2, a₄₄=5, a₄₅=3, a₄₆=6, a₄₇=6, a₄₈=7, a₄₉=5.

4.9. a₁=9, a₂=2, a₃=4, a₄=1, a₅=6, a₆=2, a₇=2, a₈=6, a₉=4, a₁₀=6, a₁₁=9, a₁₂=3, a₁₃=7, a₁₄=4, a₁₅=6, a₁₆=6, a₁₇=4, a₁₈=3, a₁₉=5, a₂₀=2, a₂₁=8, a₂₂=1, a₂₃=6, a₂₄=6, a₂₅=2, a₂₆=3, a₂₇=7, a₂₈=7, a₂₉=9, a₃₀=5, a₃₁=3, a₃₂=6, a₃₃=2, a₃₄=5, a₃₅=5, a₃₆=4, a₃₇=6, a₃₈=8, a₃₉=3, a₄₀=3, a₄₁=8, a₄₂=4, a₄₃=2, a₄₄=5, a₄₅=3, a₄₆=6, a₄₇=8, a₄₈=7, a₄₉=8.

4.10. a₁=10, a₂=5, a₃=4, a₄=1, a₅=4, a₆=2, a₇=7, a₈=3, a₉=4, a₁₀=6, a₁₁=9, a₁₂=3, a₁₃=7, a₁₄=4, a₁₅=2, a₁₆=8, a₁₇=3, a₁₈=2, a₁₉=8, a₂₀=9, a₂₁=6, a₂₂=1, a₂₃=6, a₂₄=6, a₂₅=2, a₂₆=3, a₂₇=7, a₂₈=2, a₂₉=2, a₃₀=3, a₃₁=1, a₃₂=4, a₃₃=2, a₃₄=7, a₃₅=5, a₃₆=4, a₃₇=6, a₃₈=8, a₃₉=3, a₄₀=3, a₄₁=3, a₄₂=8, a₄₃=4, a₄₄=7, a₄₅=5, a₄₆=6, a₄₇=6, a₄₈=7, a₄₉=5.

5. Для графа задания 4 найти путь наименьшего веса из вершины 1 в вершину 23.

6. Найти максимальный поток сети и разрез минимального веса.

6 .1 s

10 18

9 8 13

12 7 7 4 9 11

5 4 2 5 6 6

14 13 11 13

17 8 17

t

6 .2. s

11 16

7 3 15 17 9

7 5 8 7

5 11 7 9 7

4 12 14 6

8 10 16

t

6 .3. s

15 11

8 5 16 13

3 22 5 2 4

7 2 6 5 9

2 14 17 9

15 13

t

6 .4. s

17 12

9 9 11 9

6 7 5 9

7 4 5 6 4 7

9 7 6

11 9 8

t

6 .5. s

15 9 16

7 3 10

8 2 2 7 5 4 8 7 11

5 2 4 5

8 6

14 11 10

13

t

6 .6. s

17 5 9 10 14

11 9 5

5 3 7 4 6

9 5 7 9

4 7 11 8

15 7

t

6 .7. s

17 5 7 9 16

7 8 9 7

6 5 4 3 4 10

6 4 6

5 8

11 10 12 9

t

6 .8. s

14 9 21

5 8

7 4 3 4 7 13 7

6 2 4 10 9

3 12

8 12 7 20

t

6 .9. s

21 8 15

10 12 13

7 2 3 7 9

3 4 3 2 2 4

6 2

5 3 16

t

6 .10. s

18 10 14

9 10 12

3 5 3

7 4 5 2 9 8 10

7 9

11 10 11 20

t

7. Для заданного графа составить код Хамари и найти каноническую нумерацию вершин графа.

7.1.

7.2.

7.3.

7.4.

7.5.

7 .6.

7 .7.

7 .8.

7 .9.

7 .10.

Задание 9. Для заданного графа определить, является ли он Эйлеровым или квазиэйлеровым, и найти соответствующий цикл или цепь.

8.1.

8.2.

8.3.

8.4.

8.5.

8.6.

8.7.

8.8.

8.9.

8.10.

Задание 9. Для заданного помеченного дерева составить код Прюфера и по полученному коду восстановить исходное дерево.

9.1.

9.2.

9.3.

9.4.

9.5.

9.6.

9.7.

9.8.

9.9.

9.10.