12.2. Планарность

Обсуждение планарности в этом разделе позволяет решить вторую историческую задачу из перечисленных в подразделе 7.1.1, а также подготавливает результаты, необходимые для доказательства теоремы о пяти красках.

12.2.1. Укладка графов

Граф укладывается на некоторой поверхности, если его можно нарисовать на этой поверхности так, чтобы ребра графа при этом не пересекались. Граф назы­вается планарным, если его можно уложить на плоскости. Плоский граф — это граф, уже уложенный на плоскости.

Область, ограниченная ребрами в плоском графе, и не содержащая внутри себя вершин и ребер, называется гранью. Число граней плоского графа G обозначает­ся r(G).

ЗАМЕЧАНИЕ -

Внешняя часть плоскости также образует грань.

Пример

На рис. 12.1 показаны диаграммы планарного графа и его укладки на плоскости. Этот граф имеет 4 грани.

Рис. 12.1. Пленарный граф и его укладка