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

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

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

Вопрос звучит так: «Верно ли, что каждый планарный граф является плоским?». Здесь есть нюанс в терминологии.
Если под «является плоским» понимать «обладает свойством быть изоморфным некоторому плоскому графу» или «может быть представлен плоским образом», то ответ утвердительный по определению планарности.
Однако, строго говоря, планарность — это топологическое свойство класса графов, а плоскость — характеристика конкретного рисунка. Любой планарный граф допускает плоскую укладку. Следовательно, мы можем сказать, что любой планарный граф может быть изображён как плоский.
Но давайте посмотрим на обратную ситуацию. Существует ли планарный граф, который не является плоским? Нет, потому что если он планарный, то по определению существует его плоская диаграмма. В школьном курсе статистики и дискретной математики эти понятия часто отождествляются в контексте существования такой диаграммы.
Тем не менее, более точная формулировка ответа зависит от того, считаем ли мы «плоским» только конкретное текущее изображение. Но поскольку граф — это абстракция, то наличие хотя бы одного плоского изображения делает граф «способным быть плоским». В большинстве учебников для 10–11 классов подразумевается, что планарный граф — это тот, который можно нарисовать без пересечений. Поэтому любой планарный граф имеет плоское представление.
Важное уточнение: Часто в задачах проверяют знание того, что не всякий нарисованный граф с пересечениями является непланарным (его можно перерисовать). И наоборот, планарный граф всегда допускает плоскую запись.
Ответ на вопрос «Верно ли, что каждый планарный граф является плоским?» в рамках стандартной школьной программы трактуется как Да , если подразумевается возможность представления. Однако, если термин «плоский граф» используется для обозначения конкретного рисунка, то нужно различать объект и его модель.
Давайте проверим строгость определения. Планарный граф G — это граф, который изоморфен некоторому плоскому графу H. То есть сам по себе G не обязательно выглядит как плоский рисунок, пока мы его не нарисуем соответствующим образом. Но свойство «быть плоским» приписывается именно тем графам, которые имеют такое представление.
Следовательно, множество планарных графов совпадает с множеством графов, которые могут быть представлены как плоские. Поэтому утверждение верно в смысле возможности реализации.

Рассмотрим полный граф K₅. Он не является планарным, значит, он не может быть изображён как плоский граф (без пересечений). Значит, он не входит в класс рассматриваемых объектов.
Рассмотрим куб Q₃. Он планарен. Мы можем нарисовать его на плоскости без пересечений рёбер. Это изображение будет называться плоским. Сам граф Q₃ является планарным. Таким образом, планарный граф действительно обладает свойством быть представимым плоским образом.