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

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

а) 4 вершины степени 3 и 6 вершин степени 1;

б) 2 вершины степени 4, 2 вершины степени 3 и 8 вершин степени 1.

Для решения этой задачи мы воспользуемся двумя ключевыми свойствами графов:

1. Лемма о рукопожатиях: Сумма степеней всех вершин графа равна удвоенному числу его рёбер. $ \sum_{v \in V} \deg(v) = 2|E| $.
2. Свойство дерева: Дерево с $ |V| $ вершинами всегда имеет ровно $ |V| - 1 $ рёбер. $ |E| = |V| - 1 $.

Мы должны убедиться, что для заданных условий эти свойства выполняются, а затем построить (изобразить) пример такого дерева.

а) 4 вершины степени 3 и 6 вершин степени 1;

1. Проверка возможности существования.

Общее число вершин в графе: $ |V| = 4 + 6 = 10 $.

Сумма степеней всех вершин: $ \sum \deg(v) = 4 \cdot 3 + 6 \cdot 1 = 12 + 6 = 18 $.

Согласно лемме о рукопожатиях, число рёбер должно быть $ |E| = 18 / 2 = 9 $.

Проверим свойство дерева: для 10 вершин дерево должно иметь $ |V| - 1 = 10 - 1 = 9 $ рёбер.

Поскольку оба условия выполняются ($ |E|=9 $), такое дерево может существовать.

2. Построение и изображение.

Вершины степени 1 являются "листьями" дерева, а вершины более высокой степени — внутренними. У нас есть 4 внутренние вершины и 6 листьев.

Расположим 4 внутренние вершины (степени 3) в виде цепи. Затем добавим к ним "листья" так, чтобы их степени стали равны 3.

• Соединим 4 внутренние вершины (A, B, C, D) последовательно: A-B-C-D.
• Степени вершин A и D равны 1, а степени B и C равны 2.
• Чтобы степень A стала 3, нужно добавить 2 листа.
• Чтобы степень B стала 3, нужно добавить 1 лист.
• Чтобы степень C стала 3, нужно добавить 1 лист.
• Чтобы степень D стала 3, нужно добавить 2 листа.

Общее количество добавленных листьев: $ 2 + 1 + 1 + 2 = 6 $. Это соответствует условию задачи.

Ниже представлен один из возможных вариантов такого дерева. Внутренние вершины (степени 3) показаны синим цветом, а листья (степени 1) — серым.

Ответ: Пример дерева изображен выше.

б) 2 вершины степени 4, 2 вершины степени 3 и 8 вершин степени 1.

1. Проверка возможности существования.

Общее число вершин в графе: $ |V| = 2 + 2 + 8 = 12 $.

Сумма степеней всех вершин: $ \sum \deg(v) = 2 \cdot 4 + 2 \cdot 3 + 8 \cdot 1 = 8 + 6 + 8 = 22 $.

Согласно лемме о рукопожатиях, число рёбер должно быть $ |E| = 22 / 2 = 11 $.

Проверим свойство дерева: для 12 вершин дерево должно иметь $ |V| - 1 = 12 - 1 = 11 $ рёбер.

Условия выполняются ($ |E|=11 $), следовательно, такое дерево может существовать.

2. Построение и изображение.

У нас есть 4 внутренние вершины (две степени 4 и две степени 3) и 8 листьев (степени 1).

Построим дерево по аналогии с предыдущим пунктом, соединив 4 внутренние вершины в цепь. Для наглядности расположим вершины степени 4 по краям цепи, а вершины степени 3 — в центре.

• Соединим вершины в последовательности: A(степень 4) - B(степень 3) - C(степень 3) - D(степень 4).
• На данный момент степени вершин: $ \deg(A)=1, \deg(B)=2, \deg(C)=2, \deg(D)=1 $.
• Чтобы степень A стала 4, нужно добавить $ 4-1=3 $ листа.
• Чтобы степень B стала 3, нужно добавить $ 3-2=1 $ лист.
• Чтобы степень C стала 3, нужно добавить $ 3-2=1 $ лист.
• Чтобы степень D стала 4, нужно добавить $ 4-1=3 $ листа.

Общее количество добавленных листьев: $ 3 + 1 + 1 + 3 = 8 $. Это соответствует условию.

Ниже представлен один из возможных вариантов такого дерева. Вершины степени 4 — красные, степени 3 — синие, степени 1 (листья) — серые.

Ответ: Пример дерева изображен выше.