ТЕОРЕМА 5.3

(Критерий планарности Понтрягина-Куратовского)

Граф G является плоским или планарным тогда и только тогда, когда он не содержит подграфов, гомеоморфных графам K ₃,₃ или A ₅.

Следовательно, планарность или непланарность произвольного графа G зависит от того, содержится ли в G подграф, стягиваемый к K ₃,₃ и A ₅ или нет.

Для каждого графа G существует ровно две альтернативы:

1)граф имеет плоскую реализацию;

2) граф содержит подграф, гомеоморфный K ₃,₃ или A ₅.

Поэтому решение вопроса о планарности произвольного графа G всегда может быть получено либо построением плоской реализации G, либо нахождением такого подграфа G, который гомеоморфен одному из графов K ₃,₃ или A _5.

При этом проверить наличие или отсутствие в G подграфов, стягиваемых к K ₃,₃ или A _5, можно путем перебора всех подграфов этого графа.

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

Пример. Граф, приведенный на рис. 5.10 не является плоским:

a

1 2

B c

Рис. 5.10

Этот граф является непланарным, поскольку в нем содержится подграф, гомеоморфный K ₃,₃. На приведенном рисунке выделены вершины, соответствующие вершинам K ₃,₃.

Рис. 5.11

Граф на рис. 5.11 является планарным, поскольку он может быть изображен как

Рис. 5.12

На рис. 5.11. и 5.12. изображен один и тот же граф. При этом закрашенная точка – это вершина графа, которая на этих рисунках размещается по-разному.

Замечание. При нахождении подграфов, гомеоморфных K ₃,₃ или A ₅, необходимо учитывать, что разбиения разных ребер в K ₃,₃ или A ₅ должны представляться в непланарных графах цепочками ребер, не имеющими общих элементов, в том числе вершин. Совпадения элементов допускаются только для крайних элементов таких цепочек, соответствующих вершинам K ₃,₃ или A ₅.