Условие
Нарисуйте в тетради какое-нибудь дерево, в котором 7 вершин, причём степень 1 имеют ровно:
а) 2 вершины;
б) 4 вершины;
в) 6 вершин.
Идея решения. Вершины степени 1 — это концевые вершины. Меняем форму дерева так, чтобы концевых вершин было нужное число, но граф оставался связным и без циклов.
Решение
а) 2 вершины степени 1
Соединим 7 вершин одной цепочкой. Из двух крайних вершин выходит по одному ребру, из остальных пяти — по два.
б) 4 вершины степени 1
Возьмём центральную вершину и соединим её с тремя вершинами — это три концевые. Четвёртую ветку сделаем длиннее: от центра цепочка из трёх вершин, концевая в ней только последняя. Всего вершин и 4 концевые.
в) 6 вершин степени 1
Соединим одну центральную вершину со всеми остальными шестью («звезда»). Из каждой из шести вершин выходит одно ребро — все они концевые.
Проверяем рисунки
В каждом дереве 7 вершин, все они соединены, циклов нет. Вершины степени 1 выделены синим.
Деревья с 7 вершинами: 2, 4 и 6 вершин степени 1 (выделены синим)
Ответ
- а) цепь из 7 вершин
- б) центр + 3 короткие ветки + ветка из 3 вершин
- в) центр, соединённый с 6 вершинами
✓ Ответ проверен вычислением