Решение задачи: Висячие вершины в дереве

Задача 1. Дано: дерево, количество вершин \( n = 30 \). Найти: наименьшее и наибольшее количество вершин степени 1 (висячих вершин). Решение: 1) Наименьшее количество висячих вершин у дерева — 2. Это случай «пути», где вершины соединены последовательно в линию. 2) Наибольшее количество висячих вершин будет у «звезды», где одна центральная вершина соединена со всеми остальными. В этом случае количество висячих вершин равно \( n - 1 \). Для \( n = 30 \): \( 30 - 1 = 29 \). Ответ: наименьшее — 2, наибольшее — 29. Задача 2. а) Посчитаем вершины на рисунке: A, B, C, D, E, F, G, H, I, J, K. Всего 11 вершин. У любого дерева количество ребер \( m = n - 1 \). Значит, \( 11 - 1 = 10 \) ребер. б) Концевые (висячие) вершины — это вершины степени 1. На рисунке это: A, B, D, F, G, I, K. Всего 7 вершин. в) Висячие вершины — это то же самое, что и концевые вершины. Их 7. Ответ: а) 11 вершин, 10 ребер; б) 7; в) 7. Задача 3. Концевые вершины дерева на рисунке: A, B, P, O, K, H. Примеры цепей: а) Из двух ребер: A — C — B. б) Из трех ребер: B — C — D — E (но E не концевая), поэтому возьмем B — C — D — F (F не концевая). Правильный пример: нет цепи ровно из 3 ребер между концевыми вершинами. Проверим: B-C-D-E-P (4 ребра). По рисунку: B-C-A (2 ребра). Между концевыми вершинами в данном дереве минимально 2 ребра, далее 4 и более. Если допустить, что P, O, K, H, A, B — концевые: б) Цепь из 3 ребер: отсутствует между концевыми. в) Из шести ребер: P — E — D — F — G — N — K. г) Из семи ребер: P — E — D — F — G — N — H (6 ребер). Посчитаем до O: P — E — D — F — G — O (5 ребер). Проверим путь A — C — D — F — G — N — K: это 1(AC)+1(CD)+1(DF)+1(FG)+1(GN)+1(NK) = 6 ребер. Путь B — C — D — F — G — N — K: 6 ребер. Путь A — C — D — F — G — N — H: 6 ребер. Путь P — E — D — F — G — N — K: 6 ребер. Для 7 ребер: в данной структуре пути между концевыми вершинами имеют длину 2, 4, 5 или 6. Пути длиной 7 нет. Задача 4. Чтобы нарисовать такое дерево, можно взять центральное ребро и к его концам добавить разветвления. Математическая проверка: сумма степеней вершин равна \( 2m \). Вершины: 4 вершины степени 3 и 6 вершин степени 1. Всего \( 4 + 6 = 10 \) вершин. Ребер должно быть \( 10 - 1 = 9 \). Сумма степеней: \( 4 \cdot 3 + 6 \cdot 1 = 12 + 6 = 18 \). \( 2m = 2 \cdot 9 = 18 \). Условие выполняется. Рисунок: Нарисуйте цепочку из четырех вершин (степени 3), и к каждой «свободной» связи добавьте висячую вершину так, чтобы суммарно их стало 6. Задача 5. Граф-решетка на рисунке имеет 4 вершины по горизонтали и 5 по вертикали. Всего \( n = 4 \cdot 5 = 20 \) вершин. Посчитаем количество ребер (прутьев) в целой решетке: Горизонтальных: \( 5 \cdot 3 = 15 \). Вертикальных: \( 4 \cdot 4 = 16 \). Всего ребер \( M = 15 + 16 = 31 \). Чтобы решетка не развалилась (осталась связной) и при этом мы удалили максимум ребер, она должна превратиться в дерево. В дереве с 20 вершинами должно остаться \( n - 1 = 20 - 1 = 19 \) ребер. Количество разрезанных прутьев: \( M - (n - 1) = 31 - 19 = 12 \). Ответ: 12 прутьев.