Номер 17, страница 9, часть 2 - гдз по алгебре 7-9 класс учебник Высоцкий, Ященко

17 Изобразите какое-нибудь дерево, в котором:

а) 8 вершин, 5 из них концевые;

б) 10 вершин, 6 из них концевые.

В соответствии с условием, дерево должно иметь 8 вершин, из которых 5 являются концевыми (листьями).
- Общее число вершин: $V = 8$.
- Число концевых вершин (вершин со степенью 1): $L = 5$.
- Число внутренних вершин (вершин со степенью не менее 2): $I = V - L = 8 - 5 = 3$.
- В любом дереве число рёбер $E$ на единицу меньше числа вершин: $E = V - 1 = 8 - 1 = 7$.
- Сумма степеней всех вершин равна удвоенному числу рёбер: $\sum_{i=1}^{V} \deg(v_i) = 2E = 2 \times 7 = 14$.
Сумма степеней 5 концевых вершин равна $5 \times 1 = 5$.
Следовательно, сумма степеней 3 внутренних вершин должна быть равна $14 - 5 = 9$.
Пусть $d_1, d_2, d_3$ — степени трёх внутренних вершин. Нам нужно, чтобы $d_1, d_2, d_3 \ge 2$ и $d_1 + d_2 + d_3 = 9$. Одним из возможных наборов степеней является (2, 5, 2).

Построим такое дерево. Возьмём три внутренние вершины, назовём их A, B, C, и соединим их в виде пути A-B-C. Изначально $\deg(A)=1, \deg(B)=2, \deg(C)=1$. Нам нужно присоединить 5 листьев (назовем их 1, 2, 3, 4, 5) так, чтобы все вершины A, B, C стали внутренними (степень $\ge 2$) и было выполнено условие на сумму степеней.
- К вершине A (текущая степень 1) присоединим лист 1. Теперь $\deg(A)=2$.
- К вершине C (текущая степень 1) присоединим лист 5. Теперь $\deg(C)=2$.
- Оставшиеся три листа (2, 3, 4) присоединим к центральной вершине B. Её степень станет $2+3=5$.
В результате мы получили дерево со следующими степенями вершин:
- Внутренние вершины: $\deg(A)=2$, $\deg(B)=5$, $\deg(C)=2$.
- Концевые вершины: $\deg(1)=\deg(2)=\deg(3)=\deg(4)=\deg(5)=1$.
Общее число вершин 8 (A, B, C, 1, 2, 3, 4, 5), из них 5 концевых. Все условия выполнены.
Схематично это дерево можно изобразить так:

Ответ: Пример такого дерева показан на рисунке выше. Три внутренние вершины (A, B, C) соединены в цепь. К центральной вершине B присоединено три концевые вершины, а к крайним (A и C) — по одной.

В этом случае дерево должно иметь 10 вершин, из которых 6 являются концевыми.
- Общее число вершин: $V = 10$.
- Число концевых вершин (листьев): $L = 6$.
- Число внутренних вершин: $I = V - L = 10 - 6 = 4$.
- Число рёбер: $E = V - 1 = 10 - 1 = 9$.
- Сумма степеней всех вершин: $\sum_{i=1}^{V} \deg(v_i) = 2E = 2 \times 9 = 18$.
Сумма степеней 6 концевых вершин равна $6 \times 1 = 6$.
Следовательно, сумма степеней 4 внутренних вершин должна быть равна $18 - 6 = 12$.
Пусть $d_1, d_2, d_3, d_4$ — степени четырёх внутренних вершин. Нам нужно, чтобы $d_1, d_2, d_3, d_4 \ge 2$ и $d_1 + d_2 + d_3 + d_4 = 12$. Одним из возможных наборов степеней является (3, 3, 3, 3).

Построим дерево для набора степеней (3, 3, 3, 3).
Возьмём четыре внутренние вершины, назовём их A, B, C, D, и соединим их в виде пути: A-B-C-D. Изначально у вершин A и D степень 1, у B и C — степень 2.
Нам нужно присоединить 6 листьев (назовем их 1, 2, 3, 4, 5, 6) так, чтобы степени вершин A, B, C, D стали равны 3.
- К вершине A (текущая степень 1) нужно добавить 2 ребра. Присоединим к ней листья 1 и 2. Теперь $\deg(A)=3$.
- К вершине B (текущая степень 2) нужно добавить 1 ребро. Присоединим к ней лист 3. Теперь $\deg(B)=3$.
- К вершине C (текущая степень 2) нужно добавить 1 ребро. Присоединим к ней лист 4. Теперь $\deg(C)=3$.
- К вершине D (текущая степень 1) нужно добавить 2 ребра. Присоединим к ней листья 5 и 6. Теперь $\deg(D)=3$.
В результате мы получили дерево со следующими степенями вершин:
- Внутренние вершины: $\deg(A)=3$, $\deg(B)=3$, $\deg(C)=3$, $\deg(D)=3$.
- Концевые вершины: $\deg(1)=\deg(2)=\deg(3)=\deg(4)=\deg(5)=\deg(6)=1$.
Общее число вершин 10, из них 6 концевых. Все условия выполнены.
Схематично это дерево можно изобразить так:

Ответ: Пример такого дерева показан на рисунке выше. Четыре внутренние вершины (A, B, C, D) соединены в цепь. К крайним вершинам цепи (A и D) присоединено по две концевые вершины, а к центральным (B и C) — по одной.