Алгоритм нахождения кратчайшего остова в нагруженном графе

Пусть дан нагруженный граф G = (V,X), где V={v₁,…, v_n}, k – количество компонент связности.

1. Строим дерево Д₁, состоящее из множества вершин V и единственного ребра х₁, которое имеет минимальную длину.

2. Если граф Д_i уже построен и i<n-k, то строим граф Д_i+1, добавляя к множеству ребер графа Д_i ребро х_i+1, имеющее минимальную длину среди ребер, не входящих в Д_i и не составляющих циклов с ребрами из Д_i.

Упражнения

9.1. Найти центр, радиус и диаметр деревьев:

a) б)

в) г)

9.2. С помощью леса представить перестановки из n элементов множества M={a,b,c,d} и подсчитать их число.

9.3. На рисунке изображена схема местности. Передвигаться из пункта в пункт можно только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? У какого из этих путей наименьшая длина? У какого – наибольшая длина?

1 2 3

4 5 6

7 8 9

9.4. В игре, представленной деревом, первым делает ход игрок A. В какую из четырёх позиций должен пойти игрок A, чтобы выиграть?

1 4

2 3

A B B A

B A B A B B B A А

9.5. По кодовому дереву восстановить двоичный код алфавита {a, b, c, d, e, f, g}.

0 0 a

b

0 1

1 c

0 1 1

d

1

1 0 e

f

1 0 0

g

1

9.6. Построить кодовое дерево для кодов:

а) a=0000 б) а=00

b=0101 b=0001

c=0011 c=011

d=01 d=1100

e=100 e=1101

f=101 f=111

g=111

9

.7. Дан граф:

v₁ 1 9 v₃

1 4 1 6

2 8

5

3 7 6

С помощью дерева найти кратчайший путь из V₁ в V₇ и его длину.

9.8. Движение из пункта A₁ в пункт A₉ разрешается только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Определить число возможных путей из пункта A₁ в пункт A₉ и длину наикратчайшего из них.

A₂ A₇

A₅

4 5 7 9

A₉

10 13

3

9

A₁ 13 1

9

A₆

5 10 4 8

A₄ A

9.9. Построить остов графа. Найти цикломатическое число.

а) б)

9.10. Найти остов минимального веса нагруженного графа:

а) б)

1 1

10 8 7

4 1 2 3 2 1

9 1 3 3 3 3

2 7

6 2 1

2 2 1

5 1

1

9.11. Построить остов графа. Найти цикломатическое число. Выделить базис циклов графа. Выразить какой-либо цикл в графе через базисные циклы. Составить матрицу базисных циклов.

а) б)

в)