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

9 Сколько концевых вершин в дереве на рисунке 10?

a) б) в) Рисунок 10

Концевой (или висячей) вершиной в теории графов называется вершина, степень которой равна 1. Степень вершины — это количество рёбер, которые к ней присоединены (инцидентны ей). В случае дерева, концевые вершины часто называют "листьями". Наша задача — посчитать количество таких вершин для каждого из представленных графов.

а)

Рассмотрим граф на рисунке а). Чтобы найти все концевые вершины, нужно найти все точки, из которых выходит только одна линия (ребро). Пройдемся по всем "ветвям" дерева и посчитаем их "листья":

• Самая нижняя точка является концевой вершиной.
• На ветке, уходящей влево, есть одна концевая вершина.
• На двух небольших ветках в левой верхней части — две концевые вершины.
• На двух ветках в правой верхней части — две концевые вершины.
• На двух ветках в правой нижней части — две концевые вершины.

Суммируя все найденные концевые вершины, получаем: $1 + 1 + 2 + 2 + 2 = 8$.

Ответ: 8

б)

Рассмотрим граф на рисунке б). Этот граф симметричен и состоит из центральной части и четырех одинаковых расходящихся от нее ветвей. Каждая из этих четырех ветвей оканчивается тремя концевыми вершинами ("листьями").

Поскольку у нас 4 одинаковые группы ветвей, и в каждой группе по 3 концевые вершины, общее количество концевых вершин можно найти умножением:

$4 \times 3 = 12$.

Ответ: 12

в)

Граф на рисунке в) является простой ломаной линией, что в теории графов называется цепью или простым путем. В таком графе степень 1 имеют только две вершины: начальная и конечная. Все промежуточные вершины имеют степень 2, так как каждая из них соединена с двумя соседними вершинами.

На рисунке видно, что только крайняя левая и крайняя правая вершины соединены с графом одним ребром. Следовательно, только они являются концевыми.

Ответ: 2

10 В дереве 4 вершины. Сколько концевых вершин в нём может быть? Приведите пример дерева для каждого возможного значения.

В дереве с 4 вершинами может быть 2 или 3 концевые (листовые) вершины. Ниже представлено развернутое решение, объясняющее, почему это так, и примеры для каждого возможного случая.

Для анализа воспользуемся основными свойствами графа-дерева. Для дерева с 4 вершинами ($n=4$) справедливо следующее:
1. Количество ребер равно $m = n-1 = 4-1=3$.
2. Сумма степеней всех вершин равна удвоенному количеству ребер (согласно лемме о рукопожатиях): $\sum \text{deg}(v) = 2m = 2 \times 3 = 6$.
3. Концевая вершина — это вершина со степенью 1.
4. Любое дерево с $n \geq 2$ вершинами имеет как минимум две концевые вершины. Этот факт сразу исключает возможность существования дерева с 0 или 1 концевой вершиной.

Рассмотрим все возможные случаи для количества концевых вершин.

2 концевые вершины

Если в дереве 2 концевые вершины, то их степени равны 1. Две оставшиеся (внутренние) вершины должны иметь степень не менее 2. Обозначим степени вершин как $d_1, d_2, d_3, d_4$.
Пусть $d_1=1$ и $d_2=1$. Для двух других вершин $d_3 \geq 2$ и $d_4 \geq 2$.
Используя свойство суммы степеней: $d_1 + d_2 + d_3 + d_4 = 1 + 1 + d_3 + d_4 = 6$.
Отсюда следует, что $d_3 + d_4 = 4$.
Единственное решение для этого уравнения в целых числах при условии $d_3, d_4 \geq 2$ — это $d_3 = 2$ и $d_4 = 2$.
Таким образом, мы ищем дерево с набором степеней вершин $\{1, 1, 2, 2\}$. Такое дерево единственно (с точностью до изоморфизма) и представляет собой граф-путь (цепь).

Пример: Вершины 1, 2, 3, 4 соединены последовательно ребрами (1,2), (2,3), (3,4). Граф выглядит как 1—2—3—4. Вершины 1 и 4 имеют степень 1 и являются концевыми. Вершины 2 и 3 имеют степень 2.
Ответ: Дерево-цепь (граф-путь), в котором четыре вершины соединены последовательно, например, 1—2—3—4.

3 концевые вершины

Если в дереве 3 концевые вершины, то их степени равны 1. Оставшаяся одна вершина должна иметь степень не менее 2.
Пусть $d_1=1, d_2=1, d_3=1$. Для четвертой вершины $d_4 \geq 2$.
Сумма степеней: $d_1 + d_2 + d_3 + d_4 = 1 + 1 + 1 + d_4 = 6$.
Отсюда $3 + d_4 = 6$, что дает $d_4 = 3$.
Набор степеней вершин в таком дереве: $\{1, 1, 1, 3\}$. Этому набору соответствует граф-звезда.

Пример: Одна центральная вершина (например, вершина 4) соединена с тремя остальными (1, 2, 3). Рёбра: (4,1), (4,2), (4,3). Вершины 1, 2 и 3 не соединены между собой. Они имеют степень 1 и являются концевыми. Центральная вершина 4 имеет степень 3.
Ответ: Дерево-звезда, в котором одна центральная вершина соединена с тремя остальными.

Анализ невозможных случаев

- 0 или 1 концевая вершина: Как было упомянуто, любое дерево с 2 или более вершинами имеет как минимум 2 концевые вершины, поэтому эти случаи невозможны.
- 4 концевые вершины: Если бы все 4 вершины были концевыми, степень каждой была бы равна 1. Сумма степеней была бы $1+1+1+1 = 4$. Это противоречит тому, что сумма степеней в дереве с 4 вершинами должна быть равна 6.

11 В дереве 100 вершин. Какое в нём может быть:

а) наибольшее число концевых вершин;

б) наименьшее число концевых вершин?

а) наибольшее число концевых вершин

По определению, дерево — это связный граф без циклов. Концевой вершиной (или листом) называется вершина, степень которой равна 1 (т.е. из нее выходит ровно одно ребро). В дереве с $n$ вершинами всегда $n-1$ ребер. В нашем случае $n=100$, значит, в дереве 99 ребер.

Согласно лемме о рукопожатиях, сумма степеней всех вершин графа равна удвоенному числу ребер. Для нашего дерева: $$ \sum_{i=1}^{100} \text{deg}(v_i) = 2 \times (100 - 1) = 2 \times 99 = 198 $$ где $\text{deg}(v_i)$ — степень $i$-ой вершины.

Пусть $k$ — число концевых вершин. Тогда в дереве есть $100-k$ неконцевых (внутренних) вершин. Степень каждой концевой вершины равна 1. Степень любой внутренней вершины не может быть меньше 2 (если бы она была равна 0, вершина была бы изолированной, а граф — несвязным; если бы она была равна 1, вершина была бы концевой).

Чтобы максимизировать число концевых вершин $k$, нужно минимизировать число внутренних вершин. В любом дереве с числом вершин больше двух должна быть хотя бы одна внутренняя вершина, иначе граф будет несвязным.

Рассмотрим случай, когда в дереве есть только одна внутренняя вершина. Тогда остальные $100 - 1 = 99$ вершин являются концевыми. Такая структура возможна: одна центральная вершина соединена ребрами с 99 остальными вершинами. Этот граф называется "звезда".

В такой конфигурации:

• Центральная (внутренняя) вершина имеет степень 99.
• Каждая из 99 остальных вершин имеет степень 1, то есть является концевой.

Сумма степеней равна $1 \times 99 + 99 \times 1 = 198$, что соответствует нашим расчетам. Этот граф является деревом, так как он связный и не содержит циклов.

Таким образом, максимальное возможное число концевых вершин равно 99.

Ответ: 99

б) наименьшее число концевых вершин

Воспользуемся теми же основными положениями. Пусть $k$ — число концевых вершин. Сумма их степеней равна $k \times 1 = k$. В дереве $100-k$ внутренних вершин, и степень каждой из них не меньше 2. Следовательно, сумма их степеней не меньше чем $2 \times (100-k)$.

Общая сумма степеней всех вершин равна 198. Мы можем записать неравенство: $$ k + 2(100-k) \le 198 $$ $$ k + 200 - 2k \le 198 $$ $$ 200 - k \le 198 $$ $$ 2 \le k $$ Это означает, что в любом дереве со 100 вершинами должно быть как минимум 2 концевые вершины.

Теперь покажем, что существует дерево ровно с двумя концевыми вершинами. Чтобы минимизировать число концевых вершин, нужно, чтобы степени внутренних вершин были как можно меньше, то есть равны 2.

Рассмотрим случай, когда $k=2$. Тогда в дереве есть 2 концевые вершины и $100 - 2 = 98$ внутренних. Сумма степеней концевых вершин равна $2 \times 1 = 2$. Сумма степеней внутренних вершин должна быть $198 - 2 = 196$. Средняя степень внутренней вершины: $196 / 98 = 2$.

Поскольку минимальная степень внутренней вершины равна 2, то все 98 внутренних вершин должны иметь степень ровно 2. Граф, в котором есть 2 вершины степени 1, а остальные 98 вершин имеют степень 2, представляет собой простую цепь (путь).

Такой граф можно представить как $v_1 - v_2 - v_3 - \dots - v_{99} - v_{100}$. Вершины $v_1$ и $v_{100}$ являются концевыми (их степень равна 1), а все промежуточные 98 вершин ($v_2, \dots, v_{99}$) имеют степень 2. Этот граф является деревом, так как он связный и ацикличный.

Следовательно, минимально возможное число концевых вершин равно 2.

Ответ: 2

12 На рисунке 11 показано дерево. Рассмотрите цепи, соединяющие начальную вершину $S$ с концевыми. Сколько таких цепей имеют длину 2; длину 3; длину 4?

a) б) Рисунок 11

В задаче требуется найти количество цепей (путей) определённой длины от начальной вершины S до концевых вершин (вершин со степенью 1, т.е. "листьев" дерева). Длина цепи определяется количеством рёбер в ней.

Рассмотрим дерево, изображенное на рисунке 11а.

Сколько цепей имеет длину 2?
От вершины S отходят две ветви.

• По левой ветви: проходим одно ребро до промежуточной вершины, от которой отходят два ребра к двум концевым вершинам. Это 2 цепи длины 2.
• По правой ветви: проходим одно ребро до промежуточной вершины, от которой отходит одно ребро к концевой вершине. Это 1 цепь длины 2.

Всего цепей длины 2: $2 + 1 = 3$.

Сколько цепей имеет длину 3?

• На левой ветви все концевые вершины находятся на расстоянии 2 от S, поэтому цепей длины 3 здесь нет.
• На правой ветви от промежуточной вершины на расстоянии 1 от S отходит ребро к другой промежуточной вершине (на расстоянии 2 от S). От этой, в свою очередь, отходят два ребра к двум концевым вершинам. Это 2 цепи длины 3.

Всего цепей длины 3: $0 + 2 = 2$.

Сколько цепей имеет длину 4?
Максимальная длина цепи от вершины S до любой концевой вершины в этом дереве равна 3. Следовательно, цепей длины 4 не существует. Всего цепей длины 4: 0.

Ответ: 3 цепи длины 2; 2 цепи длины 3; 0 цепей длины 4.

Рассмотрим дерево, изображенное на рисунке 11б.

Сколько цепей имеет длину 2?
От вершины S отходят две ветви.

• По левой ветви: от промежуточной вершины на расстоянии 1 от S отходят рёбра к двум концевым вершинам. Это 2 цепи длины 2.
• По правой ветви: от промежуточной вершины на расстоянии 1 от S отходит ребро к одной концевой вершине. Это 1 цепь длины 2.

Всего цепей длины 2: $2 + 1 = 3$.

Сколько цепей имеет длину 3?

• По левой ветви: от промежуточной вершины на расстоянии 2 от S отходят рёбра к двум концевым вершинам. Это 2 цепи длины 3.
• По правой ветви: от промежуточной вершины на расстоянии 2 от S отходят рёбра к двум концевым вершинам. Это 2 цепи длины 3.

Всего цепей длины 3: $2 + 2 = 4$.

Сколько цепей имеет длину 4?

• По левой ветви: от промежуточной вершины на расстоянии 3 от S отходят рёбра к двум концевым вершинам. Это 2 цепи длины 4.
• По правой ветви: максимальная длина цепи до концевой вершины равна 3. Цепей длины 4 здесь нет.

Всего цепей длины 4: $2 + 0 = 2$.

Ответ: 3 цепи длины 2; 4 цепи длины 3; 2 цепи длины 4.

1 В дереве 10 вершин, две из которых — вершины X и Y. Сколько существует цепей, ведущих из X в Y?

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

Докажем это свойство:

• Существование: Так как дерево является связным графом, по определению связности, для любых двух вершин X и Y существует хотя бы одна цепь, их соединяющая.
• Единственность: Предположим, что между вершинами X и Y существуют две различные цепи. Если мы пройдем из X в Y по первой цепи, а затем вернемся из Y в X по второй, мы получим замкнутый маршрут. Поскольку цепи различны, этот маршрут будет содержать цикл. Однако, по определению, дерево является ациклическим графом, то есть не содержит циклов. Это противоречие означает, что наше предположение о существовании двух различных цепей неверно.

Таким образом, между любыми двумя вершинами в дереве, включая X и Y, существует ровно одна цепь. Количество вершин в дереве (в данном случае 10) не влияет на это свойство.

Ответ: 1

2 Какой может быть степень начальной вершины дерева; концевой вершины?

Для ответа на данный вопрос необходимо рассмотреть определения из теории графов, касающиеся структуры "дерево" и её вершин.

Степень вершины — это количество рёбер, которые к ней присоединены (инцидентны ей).

Дерево — это связный граф без циклов.

начальной вершины дерева

Понятие "начальная вершина" обычно относится к корневым деревьям, где одна из вершин выбирается в качестве корня. Степень корня определяется количеством его непосредственных потомков.

• Степень 0: Это возможно для дерева, состоящего из одной-единственной вершины. Эта вершина является корнем, и так как рёбер нет, её степень равна 0.
• Степень 1: Корень соединён с одним потомком. Например, в графе-цепочке (пути), если в качестве корня выбрана одна из крайних вершин.
• Степень $k \ge 1$: В общем случае корень может быть соединён с любым количеством $k$ потомков. Теоретических ограничений на максимальную степень корня нет, кроме общего числа вершин в дереве.

Таким образом, степень начальной вершины может быть любым целым неотрицательным числом.

Ответ: Степень начальной вершины дерева может быть любым целым неотрицательным числом ($0, 1, 2, 3, \ldots$).

концевой вершины

Концевая вершина (также называемая листом или висячей вершиной) — это вершина, которая является "тупиковой" в дереве.

• Степень 1: В стандартном определении для любого дерева, содержащего две или более вершин ($n \ge 2$), концевой вершиной называется вершина со степенью ровно 1. Она соединена только с одной другой вершиной. Любое нетривиальное дерево имеет как минимум два листа.
• Степень 0: Этот случай относится к вырожденному дереву, состоящему из одной вершины ($n=1$). Эта вершина не имеет рёбер, и её степень равна 0. Её можно считать концевой, так как у неё нет потомков (в контексте корневого дерева).

Вопрос "какой может быть" подразумевает перечисление всех возможных значений степени.

Ответ: Степень концевой вершины (листа), как правило, равна 1. Однако в тривиальном случае дерева из одной вершины степень этой вершины равна 0.

3 Может ли в дереве вершин быть больше, чем рёбер; рёбер быть больше, чем вершин?

Может ли в дереве вершин быть больше, чем рёбер

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

$E = V - 1$

Из этой формулы следует, что число вершин $V$ всегда на единицу больше числа рёбер $E$.

Проверим неравенство $V > E$, подставив в него формулу $E = V - 1$:

$V > V - 1$

Перенеся $V$ в правую часть, получим:

$0 > -1$

Это неравенство всегда истинно. Таким образом, в любом дереве, состоящем хотя бы из одной вершины, количество вершин всегда больше количества рёбер.

Ответ: Да, может. В любом дереве вершин всегда на одну больше, чем рёбер.

Может ли в дереве рёбер быть больше, чем вершин

Нет, не может. Снова обратимся к основному свойству дерева: $E = V - 1$.

Проверим, может ли выполняться неравенство $E > V$:

Подставим в него $E = V - 1$:

$V - 1 > V$

Вычтем из обеих частей неравенства $V$:

$-1 > 0$

Это неравенство ложно. Следовательно, в дереве не может быть рёбер больше, чем вершин. Стоит отметить, что если в связном графе количество рёбер хотя бы равно количеству вершин ($E \ge V$), то в таком графе обязательно есть цикл, и он по определению не является деревом.

Ответ: Нет, не может.