3 Нарисуйте в тетради какое-нибудь дерево, в котором 7 вершин, причём степень 1 имеют ровно: а) 2 вершины; б) 4 вершины; в) 6 вершин.

Решение:

Дерево — это связный неориентированный граф без циклов.

Степень вершины — это количество рёбер, инцидентных этой вершине.

Свойство дерева: Сумма степеней всех вершин дерева равна удвоенному числу рёбер. Для дерева с \( n \) вершинами число рёбер равно \( n-1 \). Следовательно, сумма степеней всех вершин равна \( 2(n-1) \).

а) Дерево с 7 вершинами, степень 1 имеют 2 вершины.

Пусть \( v_1, v_2, ..., v_7 \) — вершины. Степени вершин: \( d_1, d_2, ..., d_7 \).

По условию, 2 вершины имеют степень 1. Пусть \( d_1 = 1 \), \( d_2 = 1 \).

Сумма степеней = \( 1 + 1 + d_3 + d_4 + d_5 + d_6 + d_7 = 2(7-1) = 12 \).

\( d_3 + d_4 + d_5 + d_6 + d_7 = 10 \).

Пример такого дерева:

Вершины 1 и 7 имеют степень 1.

б) Дерево с 7 вершинами, степень 1 имеют 4 вершины.

Пусть \( d_1 = 1, d_2 = 1, d_3 = 1, d_4 = 1 \).

\( 1 + 1 + 1 + 1 + d_5 + d_6 + d_7 = 12 \).

\( d_5 + d_6 + d_7 = 8 \).

Пример такого дерева:

Вершины 1, 4, 5, 7 имеют степень 1.

в) Дерево с 7 вершинами, степень 1 имеют 6 вершин.

Пусть \( d_1 = 1, d_2 = 1, d_3 = 1, d_4 = 1, d_5 = 1, d_6 = 1 \).

\( 1 + 1 + 1 + 1 + 1 + 1 + d_7 = 12 \).

\( d_7 = 6 \).

Это дерево является звездой, где одна центральная вершина соединена со всеми остальными.

Вершины 1, 2, 3, 4, 5, 6 имеют степень 1, вершина 7 имеет степень 6.