7.3. Теорема Куратовского и другие характеризации планарности

В этом разделе представлены характеризации планарных графов, данные Куратовским, Вагнером, Харари и Таттом, Маклейном.

Для обсуждения характеризации Куратовского необходимо ввести понятие «гомеоморфизм графов».

Два ребра, инцидентные вершине степени 2, называются последовательными ребрами.

Пусть — последовательные ребра, инцидентные вершине v. Удаление вершины v и замена ребер ребром (и, ) называется слиянием последовательности (рис. 7.5, а).

Добавление новой вершины v на ребро посредством введения ребер называется включением последовательности (рис. 7.5, б).

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

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

Рис. 7.5. а — слиянне последовательности; б — включение последовательности.

В предыдущем разделе мы доказали, что графы непланарны. Следовательно, планарный граф не содержит подграфа, гомеоморфного графу или . Замечательно то, что Куратовскому [7.5] удалось доказать справедливость обратного.

Рис. 7.6. а — граф G; б — подграф графа G, гомеоморфный

В следующей теореме формулируется эта знаменитая характеризация планарности. Доказательство можно найти в работе [7.6].

Теорема 7.4 (Куратовского). Граф планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного графу или

Конструктивное доказательство этой теоремы дал Татт [7.71.

Для иллюстрации теоремы Куратовского рассмотрим граф G, изображенный на рис. 7.6, а. Он содержит подграф (рис. 7.6, б), который гомеоморфен графу Следовательно, граф G непланарен.

Представим теперь другую характеризацию планарности, полученную независимо авторами работ [7.8, 7.9].

Теорема 7.5. Граф планарен тогда и только тогда, когда он не содержит подграфа, стягиваемого к графу или .

Рассмотрим граф (называемый графом Петерсена), представленный на рис. 7.7. Этот граф не содержит подграфа, изоморфного графу или , однако, как известно, он непланарный. Поэтому, если мы хотим использовать критерий Куратовского для установления непланарности графа Петерсена, нам необходимо указать подграф, гомеоморфный графу или Однако его непланарность следует очевидным образом из только что приведенной характеризации, поскольку граф приводится к графу после стягивания ребер

Рис. 7.7. Граф Петерсена.

В следующем утверждении формулируется характеризация планарных графов Маклейна.

Теорема 7.6. Граф G планарен тогда и только тогда, когда в нем существует такое множество базисных циклов, что никакое ребро не присутствует более чем в двух из этих циклов.

Мы знаем, что ячейки планарного графа образуют базис подпространства циклов графа и что никакое ребро графа не присутствует более чем в двух ячейках. Это доказывает необходимость в теореме 7.6. Доказательство достаточности можно найти в работе

Другая важная характеризация планарных графов, использующая двойственные графы, обсуждается в разд. 7.5.