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

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

a) 2 вершины;

б) 4 вершины;

в) 6 вершин.

а)

Требуется построить дерево с $n=7$ вершинами, в котором ровно 2 вершины имеют степень 1. Дерево с $n$ вершинами всегда имеет $n-1$ рёбер. В нашем случае количество рёбер $m = 7 - 1 = 6$. Согласно лемме о рукопожатиях, сумма степеней всех вершин графа равна удвоенному числу рёбер: $\sum \text{deg}(v) = 2m$. Для нашего дерева сумма степеней вершин составляет $2 \times 6 = 12$.

По условию, две вершины имеют степень 1. Остальные $7-2=5$ вершин должны иметь степень не меньше 2 (поскольку в связном графе с более чем двумя вершинами не может быть вершин степени 0, а вершины степени 1 являются листьями, которых по условию ровно две). Обозначим степени этих пяти вершин как $d_i$, где $i=1...5$. Сумма степеней всех вершин: $2 \times 1 + \sum_{i=1}^{5} d_i = 12$. Следовательно, сумма степеней оставшихся пяти вершин: $\sum_{i=1}^{5} d_i = 10$.

Наиболее простой вариант — это когда все пять степеней равны 2. В этом случае набор степеней вершин дерева: $\{1, 1, 2, 2, 2, 2, 2\}$. Такое дерево существует и представляет собой граф-путь (или цепь) из 7 вершин.

Ответ: Можно нарисовать 7 вершин, расположенных в один ряд, и соединить каждую соседнюю пару вершин ребром. В результате получится граф-цепь, у которого две концевые вершины имеют степень 1, а пять промежуточных вершин — степень 2.

б)

Требуется построить дерево с $n=7$ вершинами, в котором ровно 4 вершины имеют степень 1. Как и в предыдущем пункте, дерево имеет 6 рёбер, а сумма степеней всех вершин равна 12.

По условию, четыре вершины имеют степень 1. Оставшиеся $7-4=3$ вершины должны иметь степень не меньше 2. Пусть их степени $d_1, d_2, d_3$. Сумма степеней всех вершин: $4 \times 1 + d_1+d_2+d_3 = 12$. Отсюда $d_1+d_2+d_3 = 8$.

Нам нужно найти три целых числа, каждое не меньше 2, с суммой 8. Возможный набор степеней для этих трёх вершин — $\{3, 3, 2\}$. Таким образом, искомое дерево может иметь набор степеней вершин $\{1, 1, 1, 1, 2, 3, 3\}$.

Такое дерево можно построить следующим образом: возьмём три вершины (назовём их внутренними) и соединим их в цепь. Центральная вершина в этой цепи будет иметь степень 2, а две крайние — пока что степень 1. У нас осталось 4 вершины, которые должны быть листьями. Присоединим по две из этих вершин к каждой из крайних вершин внутренней цепи. В результате степень крайних вершин внутренней цепи станет $1+2=3$. Таким образом, в полученном графе одна вершина имеет степень 2, две вершины — степень 3, и четыре вершины (листья) — степень 1, что удовлетворяет условию.

Ответ: Можно нарисовать три вершины в ряд, соединив центральную с двумя крайними. Затем к каждой из этих двух крайних вершин присоединить по две новые вершины.

в)

Требуется построить дерево с $n=7$ вершинами, в котором ровно 6 вершин имеют степень 1. Дерево по-прежнему имеет 7 вершин, 6 рёбер, и сумма степеней всех вершин равна 12.

По условию, шесть вершин имеют степень 1. Оставшаяся $7-6=1$ вершина должна иметь степень не меньше 2. Пусть её степень равна $d$. Сумма степеней всех вершин: $6 \times 1 + d = 12$. Отсюда $d = 6$.

Следовательно, мы ищем дерево, у которого одна вершина имеет степень 6, а остальные шесть вершин — степень 1. Такое дерево существует и называется графом-звездой $K_{1,6}$. Для его построения нужно взять одну вершину в качестве центральной и соединить её рёбрами со всеми остальными шестью вершинами.

Ответ: Можно нарисовать одну центральную вершину и шесть других вершин вокруг неё. Затем соединить центральную вершину ребром с каждой из шести других вершин. Центральная вершина будет иметь степень 6, а остальные шесть — степень 1.