1.5. Планарные графы

Планарные графы широко используются при решении таких задач, как прокладка различных путей и сетей на плоскости, и при проектировании микро-устройств для определения количества слоёв печатных плат.

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

Два графа называются гомеоморфными, если они изоморфны с точностью до вершины второй степени, то есть, если после удаления из них вершин 2-ой степени и объединения инцидентных им рёбер графы оказываются изоморфными (на рис. 1.26 показаны гомеоморфные графы G₁ и G₂.

Рис 1.26

Введение понятия гомеоморфности позволяет сформулировать критерий планарности графа.

Рис. 1.27

На рис. 1.27 изображены графы K₅ и K_3,3, называемые графами Понтрягина. K₅ - это полный граф с пятью вершинами (пятого порядка), двудольный граф K_3,3 – третьего порядка, возникающий при решении известной задачи о трех домах и трех колодцах.

С помощью методов математического анализа можно доказать, что графы Понтрягина планарными не являются. Понятно, что тогда не является планарным и любой граф, содержащий подграф, гомеоморфный одному из графов Понтрягина.

Имеет место следующая теорема, представляющая критерий планарности графа.

Теорема (Понтрягина – Куратовского). Граф является планарным тогда и только тогда, когда он не содержит подграфов, гомеоморфных одному из графов Понтрягина.