Тема 6. Деревья

Задание 1. Изобразите все деревья на n вершинах, n = 1, 2, 3, 4, 5; все неизоморфные деревья на n вершинах, n = 1, 2, 3, 4, 5.

Задание 2. Постройте дерево, задаваемое последовательностью степеней вершин:

;

; ;

; ;

; ;

Задание 3. Постройте дерево, задаваемое последовательностью ; .

Задание 4. Восстановите последовательность для каждого из деревьев, построенных в предыдущей задаче.

Задание 5. Для деревьев, изображенных на рисунке,

постройте их последовательности Прюффера .

Задание 6. Укажите максимальное и минимальное число висячих вершин дерева на n вершинах.

Задание 7. В некотором государстве 201 город, некоторые города соединены дорогами, так что любые 2 города соединены ровно одним путем. Сколько всего дорог в государстве?

Задание 8. Волейбольная сетка имеет вид прямоугольника клеток. Какое наибольшее число веревочек можно перерезать так, чтобы сетка распалась на куски?

Задание 9. Военная база противника расположена на 6 островах А, B, C, D, E и F, соединенных мостами. Какое минимально количество мостов (островов) достаточно взорвать, чтобы разобщить противника?

Задание 10. Докажите, что среди 7 деревьев, любое из которых имеет 6 вершин, существует 2 изоморфных.

Задание 11. Докажите, что любое дерево, имеющее не менее 2-х вершин, обладает как минимум двумя висячими вершинами.

Задание 12. Постройте все неизоморфные деревья на 8 вершинах.

Задание 13. Докажите, что связный граф останется связным после удаления тогда и только тогда, когда это ребро содержится в некотором цикле.

Задание 14. В сказочной стране «Цифра» есть 9 городов, которые называются 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией тогда и только тогда, когда двузначное число, полученное из названий городов, делится на 3. Можно ли добраться авиалинией из города 1 в город 9?

Задание 15. Каково наибольшее число ребер, которые можно убрать та, чтобы изображённый граф остался связным? Укажите три неизоморфных остовных дерева данного графа.

Задание 16. Докажите, что вершины дерева является вершиной-разрезом тогда и только тогда, когда её степень .

Задание 17. Докажите, что каждое ребро дерев – мост.

Задание 18. Докажите, что каждый связный граф на n вершинах содержит дерево на тех же вершинах.

Задание 19. Докажите, что каждый связный граф на n вершинах имеет ребро.

Задание 20. Докажите, что если к дереву добавить какое-либо ребро, то получится граф, содержащий один цикл.

Задание 21. Сколько ребер имеет лес (граф, являющийся объединением двух или нескольких деревьев) с n вершинами и k компонентами?

Задание 22. Цикломатическое число связного графа G – число ребер, удаленных для получения остовного дерева. Найдите циклохроматическое число для дерева, для графа , для графа , для графа .

Задание 23. Коциклический ранг связного графа G – число ребер, удаленных для получения остовного дерева. Найдите коциклический ранг для дерева, для графа , для граnфа , для графа .

Задание 24. Вычислите циклохроматическое число и коциклический ранг для графов: , графа Петерсена, связного k -регулярного графа на n вершинах, графов тел Платона.

Задание 25. Укажите число остовных деревьев полного графа .

Задание 26. Докажите, что каждый разрез связного графа имеет общее ребро с отовным деревом графа; каждый цикл – общее ребро с дополнением остовного дерева.

Задание 27. Какие деревья являются полными двудольными графами?

Задание 28. Докажите, что число реберно-помеченных деревьев на n вершинах равно .

Задание 29. Бинарным деревом называется дерево, каждая вершина которого имеет не более двух детей. Корнем дерева называется вершина, не имеющая родителей. Листьями называются вершины, не имеющие детей. Глубиной вершины называется длина пути от этой вершины до корня. Все вершины, имеющие глубину k, образуют k-уровень бинарного дерева. Бинарное дерево называется полным, если каждая его вершина имеет либо двух детей, либо ни одного. Полное бинарное дерево называется совершенным, если все его листья принадлежат одному и тому же уровню. На рисунке

приведен пример совершенного бинарного дерева, имеющего два уровня. Докажите, что бинарное дерево имеет ровно один корень. Найдите число вершин и число ребер совершенного бинарного дерева, имеющего n уровней. Найдите число листьев, число внутренних вершин совершенного бинарного дерева, имеющего n уровней.

Задание 30. Дайте определение тернарного дерева, полного тернарного дерева, совершенного тернарного дерева. Найдите число вершин и число ребер совершенного тернарного дерева, имеющего n уровней. Найдите число листьев, число внутренних вершин совершенного тернарного дерева, имеющего n уровней.

Задание 31. Имеется сеть дорог. Из точки А выходят человек. Половина идет по направлению l, половина – по направлению t. Дойдя до первого перекрестка, каждая группа разделяется: половина идет по направлению l, половина – по направлению t. Такое же разделение происходит на каждом перекрестке. Сколько людей придет в каждый из перекрестков тысячного ряда?