Упражнения

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 0 e

f

1 0 0

g

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

v₁ 1 9 v₃

1 4 1 6

2 8

3 7 6

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

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

A₂ A₇

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

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

а) б)

в)

§ 10. Раскраска графов. Планарные графы