Самостоятельная работа №1 План: Аксиоматические теории множеств. Нечеткие множества

Ответ на первый вопрос: – Граф планарен? – можно получить, если воспользоваться условиями планарности.
У связного плоского графа с n 3 число ребер m удовлетворяет условию

У связного плоского двудольного графа

Пример. Полный граф K₄ (рис. 23.1, а) – планарен?
В этом графе n = 4, m = 6.
Р  исунок 23.1
Подставим эти значения в условие планарности

Условие выполняется. Следовательно, граф планарен. Действительно, граф K₄ можно представить так, как показано на рис. 23.1, б.
Из рисунка ясно, что граф K₄ планарен.
Пример. Полный граф K₅ (рис. 23.1, в) – планарен?
В этом графе n = 5, m = 10.
Подставим эти значения в условие планарности

Условие не выполняется. Следовательно, граф не планарен.
Пример. Двудольный полный граф К_3,3 (рис. 23.1, г) – планарен?
В этом графе n = 6, m = 9.
Подставим эти значения в условие планарности

Условие не выполняется. Следовательно, граф не планарен.
Из примеров видно, что расположить на плоскости без пересечения ребер можно далеко не всякий граф. А вот в трехмерном пространстве так может быть изображен любой конечный граф.
Доказательство простое.
Расположим все вершины на одной прямой рис. 23.2.
Р  исунок 23.2
Построим m плоскостей на этой прямой, т. е. для каждого ребра свою плоскость.
Проведем ребра на своих плоскостях. Ребра не пересекаются (кроме как на своих вершинах).
Непланарность графов K₅ и К_3,3 используется для оценки планарности “больших графов”: граф не планарен, если он содержит подграфы вида K₅ или К_3,3, или сводимые к ним.
Грани плоского графа
У плоского графа кроме вершин и ребер можно выделить еще один геометрический образ – грань.
Область плоскости, ограниченная ребрами связного плоского графа и не содержащая внутри себя ни ребер, ни вершин, называется его гранью.
Внешняя неограниченная грань называется бесконечной гранью.
Например, граф на рис. 23.1, б обладает четырьмя гранями: f₁, f₂, f₃, f₄, где f₄ бесконечная грань.
У графа без циклов ровно одна грань – бесконечная. Не следует думать, что она какая–то исключительная. При укладке графа на сферу эта грань ничем не будет отличаться от других.
Число граней f в связном плоском графе определяется из соотношения
f = m – n + 2,
где n – число вершин, m – число ребер.

23.2.3 Алгоритм построения плоского изображения графа