Условие
Придумайте и нарисуйте в тетради:
а) два неодинаковых дерева с четырьмя вершинами;
б) три неодинаковых дерева с пятью вершинами.
Идея решения. Деревья неодинаковые, если одно нельзя получить из другого, просто передвинув вершины и не меняя, какие из них соединены.
Решение
а) Деревья с 4 вершинами
Первое — цепь: вершины соединены одна за другой. Второе — «звезда»: одна вершина соединена с тремя остальными.
Два неодинаковых дерева с 4 вершинами: цепь и «звезда» Почему они разные
В «звезде» есть вершина, из которой выходят 3 ребра, а в цепи из каждой вершины выходит не больше двух рёбер. Значит, деревья неодинаковые.
б) Деревья с 5 вершинами
Цепь из 5 вершин; «звезда» — центр, соединённый с четырьмя вершинами; «вилка» — вершина с тремя рёбрами, у которой одна ветка длиннее.
Три неодинаковых дерева с 5 вершинами: цепь, «звезда», «вилка» Почему они разные
Наибольшее число рёбер у одной вершины: в цепи — 2, в «вилке» — 3, в «звезде» — 4. Раз эти числа разные, и деревья неодинаковые.
Ответ
- а) цепь и «звезда»
- б) цепь, «звезда» и «вилка»
✓ Ответ проверен вычислением