Вопросы к пункту 4 «Планарные графы» на странице 65, ГДЗ по алгебре за 10 класс к учебнику Бунимовича вероятность и статистика

Вопросы к пункту 4 «Планарные графы».

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

Ответ: планарный граф — тот, который можно изобразить на плоскости без пересечения рёбер.

Возьмём граф с четырьмя вершинами \(a\), \(b\), \(c\), \(d\), в котором соединена каждая пара вершин: рёбра \(ab\), \(ac\), \(ad\), \(bc\), \(bd\), \(cd\) — всего 6. Нарисуем треугольник \(acd\), а вершину \(b\) поместим внутрь него и соединим с \(a\), \(c\) и \(d\). Рёбра нигде не пересекаются, значит, это изображение — плоский граф.

Ответ: плоский граф — например, четыре вершины, соединённые всеми шестью рёбрами: треугольник с четвёртой вершиной внутри, соединённой с тремя его вершинами.

Пример — полный граф с пятью вершинами: пять вершин, соединённых всеми возможными рёбрами, которых \(\frac{5 \cdot 4}{2} = 10\). По теореме Понтрягина — Куратовского такой граф на плоскости без пересечения рёбер изобразить невозможно.

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

Ответ: непланарен, например, полный граф с пятью вершинами; другой пример — граф о трёх домиках и трёх колодцах.

Да. Любое дерево можно нарисовать без пересечения рёбер: достаточно выбрать какую-нибудь вершину корнем, поместить её выше всех остальных, на следующем ярусе разместить её соседей, ниже — их соседей и так далее. Каждое ребро при этом соединяет вершину с её единственным предком на соседнем ярусе, и линии не пересекаются.

Ответ: да, всякое дерево планарно — его достаточно нарисовать по ярусам от выбранного корня.