10.3Задачи для самостоятельного решения
1.Найти минимальный остов графа, заданного списком взвешенных ребер:
1.({v0, v1}, 3), ({v0, v4}, 3), ({v0, v2}, 4), ({v1, v3}, 3),({v1, v6}, 4), ({v1, v4}, 4), ({v2, v4}, 1), ({v2, v7}, 1), ({v2, v5}, 3), ({v3, v6}, 3), ({v4, v6}, 2), ({v4, v8}, 3), ({v4, v7}, 1), ({v5, v7}, 1), ({v6, v8}, 2), ({v7, v8}, 2);
2.({v0, v1}, 4), ({v0, v4}, 5), ({v0, v2}, 4), ({v1, v3}, 3), ({v1, v6}, 3), ({v1, v4}, 3), ({v2, v4}, 4), ({v2, v7}, 6), ({v2, v5}, 5), ({v3, v6}, 4), ({v4, v6}, 3), ({v4, v8}, 5), ({v4, v7}, 6), ({v5, v7}, 5), ({v6, v8}, 6), ({v7, v8}, 5);
3.({v0, v1}, 4), ({v0, v4}, 4), ({v0, v2}, 4), ({v1, v3}, 2), ({v1, v6}, 5), ({v1, v4}, 2), ({v2, v4}, 3), ({v2, v7}, 5), ({v2, v5}, 3), ({v3, v6}, 2), ({v4, v6}, 2), ({v4, v8}, 5), ({v4, v7}, 3), ({v5, v7}, 3), ({v6, v8}, 5), ({v7, v8}, 4).
2.Найти остов минимальной длины графа G, в котором длины ребер равны соответствующим элементам aij матрицы A.
|
|
|
|
|
@s |
|
|
a24 |
|
@s |
|
|
|
|
|
|
|
|
|
|
|
a14 |
@ |
|
|
a36 |
@ |
|
|
|
|
|
|
|
|
|
|
|
|
|
@a25 |
|
|
|
|
@a46 |
|
|
|
|
|
|
|
|
|
|
a15 |
|
@@@ |
|
a41 |
|
@@@ |
|
|
|
|
a11 |
@s @ |
|
|
a26 |
@s |
@ |
|
|
a51 |
@s |
@ |
|
|
|
|
|
@a16 |
|
|
|
|
@a42 |
|
|
|
|
@a55 |
|
|
|
|
@ |
|
|
|
|
a32 @ |
|
|
|
|
|
|
|
|
@ |
|
|
|
a |
12 |
@ |
@ |
a |
31 |
|
|
|
@ |
@ |
|
a |
52 |
|
@ |
|
|
|
|
|
|
|
|
|
|
|
|
|
@ |
|
s@@ |
|
|
|
a21 |
@s |
@ |
|
|
|
a43 |
@s |
@ |
|
|
|
a56 |
|
s |
@a13 |
|
|
|
|
|
@a33 |
|
|
|
|
|
@a53 |
|
|
|
|
@@@ |
|
a22 |
|
@@@ |
|
a44 |
|
@@@ |
|
|
|
|
|
s@@ |
|
|
a34 |
@s |
@ |
|
|
|
|
|
s |
|
|
|
|
|
|
|
@a23 |
|
|
a35 |
@a45 |
|
a54 |
|
|
|
|
|
|
|
|
|
|
@@@ |
@@@ |
|
|
|
|
|
|
|
|
|
|
|
|
|
s |
|
|
|
|
|
|
|
s |
|
|
|
|
|
|
|