ГДЗ по вероятности и статистике, 10 класс, Высоцкий, номер 93: Изоморфные графы. Плоские и планарные графы

Вспомним основные свойства деревьев:

• Дерево с n вершинами всегда имеет n-1 ребро.
• Сумма степеней всех вершин в любом графе равна удвоенному числу рёбер (2m).

По условию у нас m=5 рёбер. Следовательно, количество вершин n равно:

Итак, нам нужно построить дерево из 6 вершин и 5 рёбер.

Обозначим степени вершин как d_1,d_2,…,d₆. По теореме о рукопожатиях:

Нам известно, что есть 3 концевые вершины. Степень концевой вершины равна 1. Значит, три вершины имеют степень 1.

Осталось распределить оставшуюся сумму степеней между остальными 6-3=3 вершинами. Сумма степеней этих трёх вершин должна быть:

Так как дерево связно и не содержит циклов, внутренние вершины должны иметь степень не менее 2 (если бы была вершина степени 0, граф был бы несвязным; если бы все оставшиеся были степени 1, это противоречило бы структуре дерева с заданными параметрами). Однако, давайте попробуем подобрать конкретные значения. Пусть степени трёх внутренних вершин будут a,b,c. Тогда a+b+c=7. Возможные варианты целых чисел ≥2: например, 3,2,2 или 4,2,1 (но 1 уже занято концевыми, так что внутренние не могут быть 1 по определению конца, хотя формально вершина степени 1 — это лист. Если мы хотим ровно 3 листа, то остальные 3 вершины не должны быть листами, то есть их степень ≥2).

Подходящий набор степеней для всех 6 вершин: 1,1,1,2,2,3. Проверка суммы: 1+1+1+2+2+3=10. Всё верно.

Построим дерево на основе набора степеней {1,1,1,2,2,3}.

1. Возьмём вершину степени 3 (назовём её A). Она будет соединена с тремя другими вершинами.
2. Чтобы получить вершины степени 2, можно сделать цепочку. Например, от A идёт ребро к вершине B (степень 2), от B к вершине C (степень 2).
3. Теперь подключим листья (вершины степени 1).
   • Вершина A (степень 3) уже имеет одно ребро к B. Ей нужно ещё два ребра к листьям. Подключим листы L₁ и L₂ к A.
   • Вершина B (степень 2) имеет ребра к A и C. Степень исчерпана.
   • Вершина C (степень 2) имеет ребро к B. Ей нужно ещё одно ребро к листу L₃.

Проверим полученную структуру:

• Вершины: A,B,C,L_1,L_2,L₃ (всего 6).
• Рёбра: (A,B),(B,C),(A,L₁),(A,L₂),(C,L₃) (всего 5).
• Степени:
  • deg(A)=3 (соседи B,L_1,L₂)
  • deg(B)=2 (соседи A,C)
  • deg(C)=2 (соседи B,L₃)
  • deg(L₁)=1
  • deg(L₂)=1
  • deg(L₃)=1
• Количество листьев (концевых вершин): 3 (L_1,L_2,L₃).
• Граф связен и не имеет циклов (это дерево).

Можно рассмотреть другой вариант распределения степеней, например, 1,1,1,2,2,3 — он единственный с точностью до перестановки, если требовать ровно 3 листа. Но структура может выглядеть иначе визуально.

Например, центральная вершина степени 3 соединена с одной вершиной степени 2 и двумя листьями. Эта вершина степени 2 соединена с другой вершиной степени 2, которая соединена с последним листом. Это тот же самый случай, что и выше.

Ещё один способ представить: возьмите путь из 4 вершин P₁-P₂-P₃-P₄. У него 2 листа (P_1,P₄) и 2 внутренние вершины (P_2,P₃). Добавьте к P₂ лист P₅, а к P₃ лист P₆. Тогда степени: P₁(1),P₂(3),P₃(3),P₄(1),P₅(1),P₆(1). Листьев 4. Не подходит. Давайте вернемся к нашему первому построению, оно корректно.