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

13 Нарисуйте какое-нибудь дерево, в котором из начальной вершины к конце-вым ведут:

a) ровно 3 цепи длины 2;

б) 2 цепи длины 1 и 4 цепи длины 2.

а) ровно 3 цепи длины 2;

Для построения такого дерева нам нужна начальная вершина (корень), из которой к концевым вершинам (листьям) ведут ровно три пути, и каждый из них имеет длину 2. Путь длины 2 состоит из двух рёбер и трёх вершин. Обозначим начальную вершину как $V_0$. Чтобы создать путь длины 2, должен существовать хотя бы один промежуточный узел.

Простейший способ удовлетворить условию — это создать дерево, в котором все пути от корня до листьев имеют длину 2, и таких листьев ровно три. Пусть из начальной вершины $V_0$ выходит одно ребро к промежуточной вершине $V_1$. Из вершины $V_1$ будут выходить три ребра к трём разным концевым вершинам: $L_1, L_2, L_3$.

В результате мы получаем следующие цепи (пути) от начальной вершины к концевым:

• $V_0 \rightarrow V_1 \rightarrow L_1$ (длина 2)
• $V_0 \rightarrow V_1 \rightarrow L_2$ (длина 2)
• $V_0 \rightarrow V_1 \rightarrow L_3$ (длина 2)

В этом дереве ровно 3 концевые вершины ($L_1, L_2, L_3$), и путь к каждой из них от начальной вершины имеет длину 2. Других концевых вершин и, следовательно, других путей к ним нет. Таким образом, условие выполнено.

Схематическое изображение такого дерева:

Ответ: Пример такого дерева представлен на схеме выше. Оно состоит из 5 вершин: начальной $V_0$, промежуточной $V_1$ и трёх концевых $L_1, L_2, L_3$. Рёбра: $(V_0, V_1), (V_1, L_1), (V_1, L_2), (V_1, L_3)$.

б) 2 цепи длины 1 и 4 цепи длины 2.

В этом случае нам нужно построить дерево, в котором от начальной вершины $V_0$ есть пути двух разных длин к концевым вершинам.

Цепи длины 1: Путь длины 1 от начальной вершины к концевой означает, что начальная вершина напрямую соединена ребром с концевой вершиной (листом). Чтобы иметь две такие цепи, нужно соединить начальную вершину $V_0$ с двумя листьями, назовём их $L_1$ и $L_2$. Пути будут $V_0 \rightarrow L_1$ и $V_0 \rightarrow L_2$.

Цепи длины 2: Аналогично пункту а), для создания четырёх цепей длины 2 нам нужны пути вида $V_0 \rightarrow V_i \rightarrow L_j$. Мы можем создать одну промежуточную вершину $V_1$, соединённую с $V_0$. Затем из $V_1$ провести рёбра к четырём новым листьям: $L_3, L_4, L_5, L_6$.

Объединив эти два условия, получаем дерево со следующей структурой:

• Начальная вершина $V_0$ соединена с двумя листьями ($L_1, L_2$) и одной промежуточной вершиной ($V_1$).
• Промежуточная вершина $V_1$ соединена с четырьмя листьями ($L_3, L_4, L_5, L_6$).

В этом дереве всего 6 концевых вершин ($L_1, ..., L_6$). Пути к ним от $V_0$:

• $V_0 \rightarrow L_1$ (длина 1)
• $V_0 \rightarrow L_2$ (длина 1)
• $V_0 \rightarrow V_1 \rightarrow L_3$ (длина 2)
• $V_0 \rightarrow V_1 \rightarrow L_4$ (длина 2)
• $V_0 \rightarrow V_1 \rightarrow L_5$ (длина 2)
• $V_0 \rightarrow V_1 \rightarrow L_6$ (длина 2)

Всего имеем 2 цепи длины 1 и 4 цепи длины 2, что соответствует условию.

Схематическое изображение такого дерева:

Ответ: Пример такого дерева представлен на схеме выше. Оно состоит из 8 вершин: начальной $V_0$, двух концевых на расстоянии 1 ($L_1, L_2$), одной промежуточной $V_1$ и четырёх концевых на расстоянии 2 ($L_3, L_4, L_5, L_6$).