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

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

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

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

а)

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

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

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

Ответ: 8

б)

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

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

$4 \times 3 = 12$.

Ответ: 12

в)

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

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

Ответ: 2