Раздел 5 «Графы»

1. Описать граф, заданный матрицей смежности, используя как можно больше характеристик. Составить матрицу инцидентности и связности (сильной связности).

2. Пользуясь алгоритмом Форда-Беллмана, найти минимальный путь из x ₁ в x ₇ в ориентированном графе, заданном матрицей весов.

3. Пользуясь алгоритмом Краскала, найти минимальное остовное дерево для графа, заданного матрицей длин ребер.

Варианты заданий

1. 1. 0 1 1 0 1 1 2. ¥ 4 6 12 ¥ ¥ ¥ 3. ¥ 12 6 20 14

1 0 0 1 0 0 ¥ ¥ ¥ 13 7 ¥ ¥ 12 ¥ 2 4 6

1 0 0 0 1 0 ¥ ¥ ¥ 5 ¥ 3 ¥ 6 2 ¥ 10 12

0 1 0 0 1 0 ¥ ¥ ¥ ¥ 10 9 ¥ 20 4 10 ¥ 6

1 0 1 1 0 1 ¥ ¥ ¥ ¥ ¥ ¥ 8 14 6 12 6 ¥

1 0 0 0 1 0 ¥ ¥ ¥ ¥ ¥ ¥ 11

¥ ¥ ¥ ¥ ¥ ¥ ¥

2. 1. 0 0 0 0 0 1 2. ¥ 1 3 9 ¥ ¥ ¥ 3. ¥ 1 ¥ 4 5

0 0 1 1 1 0 ¥ ¥ ¥ 10 4 ¥ ¥ 1 ¥ 2 ¥ 1

0 0 0 0 0 0 ¥ ¥ ¥ 2 ¥ 1 ¥ ¥ 2 ¥ 1 1

1 0 0 0 0 1 ¥ ¥ ¥ ¥ 7 6 ¥ 4 ¥ 1 ¥ 3

1 0 1 0 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 5 5 1 1 3 ¥

1 0 1 0 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 8

¥ ¥ ¥ ¥ ¥ ¥ ¥

3. 1. 0 1 0 1 0 0 2. ¥ 3 5 11 ¥ ¥ ¥ 3. ¥ 6 3 10 7

1 0 0 1 0 0 ¥ ¥ ¥ 12 6 ¥ ¥ 6 ¥ 1 2 3

0 0 0 0 1 1 ¥ ¥ ¥ 3 ¥ 2 ¥ 3 1 ¥ 5 6

1 1 0 0 1 1 ¥ ¥ ¥ ¥ 9 8 ¥ 10 2 5 ¥ 3

0 0 1 1 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 7 7 3 6 3 ¥

0 0 1 1 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 10

¥ ¥ ¥ ¥ ¥ ¥ ¥

4. 1.0 0 0 0 0 1 2. ¥ ¥ 5 4 2 2 9 3. ¥ 7 2 11 7

1 0 1 0 1 1 ¥ ¥ 1 1 ¥ 1 1 7 ¥ 3 ¥ 4

1 0 0 0 0 0 2 ¥ ¥ 1 1 ¥ 3 2 3 ¥ 1 5

0 0 1 0 0 1 ¥ 2 1 ¥ 1 ¥ ¥ 11 ¥ 1 ¥ 3

0 1 1 1 0 0 ¥ ¥ 2 2 ¥ 1 6 7 4 5 3 ¥

0 0 1 0 0 0 1 5 ¥ 1 1 ¥ ¥

2 ¥ 1 ¥ 1 2 ¥

5. 1. 0 0 0 1 1 0 2. ¥ 4 ¥ ¥ 3 1 ¥ 3. ¥ 2 ¥ 5 5

0 0 0 1 0 1 3 ¥ 2 1 ¥ ¥ 4 2 ¥ 8 ¥ 7

1 0 0 0 0 0 1 1 ¥ ¥ ¥ ¥ 1 ¥ 8 ¥ 10 1

0 1 0 0 0 1 ¥ 3 1 ¥ 1 ¥ ¥ 5 ¥ 10 ¥ 13

1 0 0 0 0 0 ¥ ¥ 2 ¥ ¥ 1 5 5 7 1 13 ¥

0 1 0 1 0 0 ¥ 3 ¥ 2 2 ¥ ¥

¥ ¥ 2 ¥ ¥ 2 ¥

6. 1. 0 0 1 0 1 0 2. ¥ ¥ 9 ¥ ¥ 2 12 3. ¥ 1 5 4 5

0 0 1 1 1 1 1 ¥ ¥ ¥ 1 2 4 1 ¥ 2 6 1

1 1 0 0 1 0 2 1 ¥ ¥ 1 ¥ 2 5 2 ¥ 1 7

0 1 0 0 0 1 ¥ 1 1 ¥ ¥ 1 ¥ 4 6 1 ¥ 4

1 1 1 0 0 0 1 2 ¥ 2 ¥ ¥ ¥ 5 1 7 4 ¥

0 1 0 1 0 0 ¥ ¥ ¥ ¥ 1 ¥ 8

¥ 2 1 ¥ 1 2 ¥

7. 1. 0 0 1 1 0 0 2. ¥ 3 4 9 ¥ ¥ ¥ 3. ¥ 4 3 5 6

1 0 0 0 0 1 12 ¥ ¥ 10 4 ¥ ¥ 4 ¥ 2 ¥ 1

1 0 0 0 1 0 ¥ ¥ ¥ 2 ¥ 1 ¥ 3 2 ¥ 1 1

0 1 0 0 0 1 ¥ ¥ ¥ ¥ 7 6 ¥ 5 ¥ 1 ¥ 3

0 0 1 0 1 0 ¥ ¥ ¥ ¥ ¥ ¥ 5 6 1 1 3 ¥

0 1 0 1 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 8

¥ ¥ ¥ ¥ ¥ ¥ ¥

8. 1. 0 1 1 0 1 1 2. ¥ 2 5 8 9 ¥ ¥ 3. ¥ 1 3 4 5

1 0 1 1 0 1 ¥ ¥ ¥ 10 4 ¥ ¥ 1 ¥ 2 9 1

1 1 0 0 1 1 5 3 ¥ 2 1 ¥ ¥ 3 2 ¥ 1 1

0 1 0 0 0 1 ¥ ¥ ¥ ¥ 7 6 ¥ 4 9 1 ¥ 3

1 0 1 0 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 5 5 1 1 3 ¥

1 1 1 1 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 9

¥ ¥ ¥ ¥ ¥ ¥ ¥

9. 1. 0 1 0 1 1 1 2. ¥ 2 5 14 ¥ ¥ ¥ 3. ¥ 5 3 10 7

1 0 0 1 0 0 11 ¥ ¥ 12 6 ¥ ¥ 5 ¥ 1 2 4

0 0 0 1 1 0 ¥ ¥ ¥ 3 ¥ 2 ¥ 3 1 ¥ 5 6

1 1 1 0 1 0 ¥ ¥ ¥ ¥ 9 8 ¥ 10 2 5 ¥ 3

1 0 1 1 0 1 ¥ ¥ ¥ ¥ ¥ ¥ 7 7 4 6 3 ¥

1 0 0 0 1 0 ¥ ¥ ¥ ¥ ¥ ¥ 10

¥ ¥ ¥ ¥ ¥ ¥ ¥

10. 10 1 1 0 1 1 2. ¥ ¥ 5 4 2 3 9 3. ¥ 7 2 11 7

1 0 0 1 1 1 ¥ ¥ 1 1 ¥ 1 6 7 ¥ 3 ¥ 4

1 0 0 0 1 0 4 ¥ ¥ 1 1 ¥ 3 2 3 ¥ 1 5

0 1 0 0 0 1 ¥ 2 1 ¥ 1 ¥ ¥ 11 ¥ 1 ¥ 3

1 1 1 0 0 1 ¥ ¥ 2 2 ¥ 1 6 7 4 5 3 ¥

1 1 0 1 1 0 1 5 ¥ 1 1 ¥ ¥

2 ¥ 1 ¥ 1 2 ¥