Упражнения

1. Нарисуйте все попарно неизоморфные деревья седьмого порядка.

2. Найдите дерево минимального порядка n  2 с тождествен­ной группой автоморфизмов.

3. Докажите, что центр дерева состоит из одной вершины в случае, когда диаметр этого дерева является четным числом, и из двух смежных вершин, когда диаметр — число нечетное.

4. Докажите, что радиус r(G) и диаметр d(G) любого дерева G связаны соотношением

r(G)=]d(G)/2.

5. Верно ли, что если диаметр связного графа G равен k (k > 2), то в G существует остовное дерево, диаметр которого так­ же равен k?

6.(n, m)-граф называется сбалансированным, если никакой его подграф не имеет вершин степени большей, чем 2т/n. Пока­жите, что всякое дерево при n > 2 — несбалансированный граф.

7.Найдите остовные деревья в К₅, Кз,з и в графе Петерсена.

8.Докажите, что подграф H графа G является в G остовом тогда и только тогда, когда верны равенства \Н\ = \G\, m (H) = \G\-k(G), k(H)=k(G).

6. Используя матричную теорему Кирхгофа, найдите число остовных деревьев в полном двудольном графе К_тn.

10. Докажите, что число помеченных двудольных деревьев с числами вершин в долях т и n равно т^n-1n^т-1.

11. Покажите, как найти остов графа с помощью поиска в ширину.

12. Постройте такое множество U точек на плоскости, для ко­торого вес дерева Штейнера был бы меньше веса любого остовного дерева графа K(U).