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

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$).

14 Сколько вершин в дереве, в котором:

а) $14$ рёбер;

б) $27$ рёбер;

в) $31$ ребро?

Для решения этой задачи необходимо использовать основное свойство дерева в теории графов. Дерево представляет собой связный граф без циклов. Для любого дерева, имеющего $V$ вершин и $E$ рёбер, всегда справедливо соотношение: $V = E + 1$. Это означает, что количество вершин в дереве всегда на единицу больше, чем количество рёбер. Используя эту формулу, найдём количество вершин для каждого случая.

По условию, в дереве 14 рёбер. Следовательно, $E = 14$.
Чтобы найти количество вершин $V$, подставим значение $E$ в формулу:
$V = 14 + 1 = 15$
Таким образом, в дереве 15 вершин.
Ответ: 15 вершин.

В данном случае в дереве 27 рёбер, то есть $E = 27$.
Применим ту же формулу для нахождения количества вершин $V$:
$V = 27 + 1 = 28$
Следовательно, в дереве 28 вершин.
Ответ: 28 вершин.

Дано, что в дереве 31 ребро, а значит $E = 31$.
Используем формулу $V = E + 1$ для расчёта количества вершин $V$:
$V = 31 + 1 = 32$
В этом дереве 32 вершины.
Ответ: 32 вершины.

15 Сколько рёбер в дереве, в котором:

а) 87 вершин;

б) 487 вершин;

в) 317 вершин?

В теории графов дерево — это связный граф, не содержащий циклов. Одно из ключевых свойств любого дерева связывает количество его вершин и рёбер. Для любого дерева с $V$ вершинами и $E$ рёбрами всегда выполняется следующее соотношение:

$E = V - 1$

Это означает, что количество рёбер в дереве всегда на единицу меньше количества вершин. Используя эту формулу, мы можем найти количество рёбер для каждого случая.

а)

Дано дерево с 87 вершинами. Чтобы найти количество рёбер, вычтем 1 из количества вершин:

$E = 87 - 1 = 86$

Ответ: 86

б)

Дано дерево с 487 вершинами. Применяем ту же формулу:

$E = 487 - 1 = 486$

Ответ: 486

в)

Дано дерево с 317 вершинами. Количество рёбер будет:

$E = 317 - 1 = 316$

Ответ: 316

16 Будет ли связным граф, который получится из дерева, если из него удалить:

а) ребро, связывающее две неконцевые вершины;

б) концевую вершину вместе с выходящим из неё ребром?

а) ребро, связывающее две неконцевые вершины;

По определению, дерево — это связный ациклический граф. Одно из ключевых свойств дерева заключается в том, что между любыми двумя его вершинами существует ровно один простой путь. Каждое ребро в дереве является мостом, то есть его удаление увеличивает число компонент связности.

Пусть $T = (V, E)$ — исходное дерево. Удалим из него ребро $e = (u, v)$, где $u$ и $v$ — неконцевые вершины (то есть их степень больше единицы: $\text{deg}(u) > 1$ и $\text{deg}(v) > 1$). Получим новый граф $T' = (V, E \setminus \{e\})$.

В исходном дереве $T$ между вершинами $u$ и $v$ был уникальный путь, состоящий из одного ребра $e$. После удаления этого ребра в графе $T'$ путь между $u$ и $v$ исчезает. Если бы существовал какой-то другой путь между $u$ и $v$ в $T'$, то этот путь существовал бы и в исходном графе $T$. Тогда в $T$ было бы как минимум два различных пути между $u$ и $v$: один по ребру $e$, а другой — альтернативный. Наличие двух путей означало бы существование цикла, что противоречит определению дерева.

Таким образом, после удаления ребра $e$ вершины $u$ и $v$ оказываются в разных компонентах связности. Это означает, что граф $T'$ становится несвязным. Он распадается на два подграфа (два меньших дерева). Условие, что вершины неконцевые, этого факта не меняет.

Ответ: нет, не будет.

б) концевую вершину вместе с выходящим из неё ребром?

Пусть $T = (V, E)$ — исходное дерево. Концевая вершина (или лист) — это вершина, степень которой равна 1. Обозначим эту вершину как $l$, а единственное инцидентное ей ребро как $e = (l, u)$, где $u$ — смежная с $l$ вершина. Мы удаляем вершину $l$ и ребро $e$, получая новый граф $T' = (V \setminus \{l\}, E \setminus \{e\})$.

Чтобы проверить связность графа $T'$, нужно показать, что между любыми двумя его вершинами существует путь. Возьмём две произвольные различные вершины $x$ и $y$ из множества вершин графа $T'$. Эти вершины также принадлежат и исходному дереву $T$.

Поскольку $T$ — связный граф, в нём существует уникальный простой путь $P$, соединяющий вершины $x$ и $y$. Этот путь не может проходить через вершину $l$, так как $l$ — концевая вершина ($\text{deg}(l)=1$). Любой путь, содержащий вершину $l$, должен либо начинаться, либо заканчиваться в ней. Он не может "пройти сквозь" $l$, так как для этого вершина должна иметь степень не менее двух.

Поскольку ни $x$, ни $y$ не являются вершиной $l$, путь $P$ между ними в графе $T$ не содержит ни вершину $l$, ни инцидентное ей ребро $e$. Это означает, что весь путь $P$ состоит из вершин и рёбер, которые не были удалены и остались в графе $T'$.

Следовательно, для любой пары вершин в $T'$ существует путь, соединяющий их. Это доказывает, что полученный граф $T'$ является связным.

Ответ: да, будет.

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) — по одной.

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 (листья) — серые.

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