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

Рассмотрим бесконечную цепочку вершин, пронумерованных натуральными числами: v_1,v_2,v_3,…. Соединим каждую вершину v_i с вершиной v_i+1 ребром (v_i,v_i+1) для всех i≥1.

Проверим свойства полученного графа:

• Связность: Любые две вершины v_i и v_j соединены путём вдоль цепочки.
• Отсутствие циклов: Граф является простой цепью, в нём нет замкнутых путей.
• Концевые вершины: Вершина v₁ имеет степень 1 (соединена только с v₂), значит, она концевая. Любая другая вершина v_k при k>1 имеет степень 2 (соединена с v_k-1 и v_k+1), значит, не является концевой.

Таким образом, мы получили бесконечное дерево с ровно одной концевой вершиной.

Рассмотрим «бесконечную звезду» или «гребёнку». Возьмём центральную вершину c. К ней присоединим бесконечное множество лучей разной длины или просто бесконечное множество рёбер, ведущих к разным вершинам.

Более простой пример: возьмём бесконечную цепочку u_1,u_2,u_3,… как в пункте а). Теперь к каждой вершине u_i добавим ещё одно ребро, ведущее к новой вершине w_i. То есть, у нас есть вершины u_i и w_i, где w_i соединено только с u_i.

Проверим свойства:

• Дерево: Исходная цепочка была деревом. Добавление новых листьев w_i не создаёт циклов, так как каждая новая вершина имеет степень 1 и соединяется с существующей частью графа единственным ребром. Граф остаётся связным.
• Концевые вершины: Каждая вершина w_i имеет степень 1, следовательно, является концевой. Поскольку индексов i бесконечно много (i=1,2,3,…), то и концевых вершин w_i бесконечно много.

Таким образом, этот граф является бесконечным деревом с бесконечным числом концевых вершин.