Теорема Понтрягина — Куратовского

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Теорема Понтрягина — Куратовского, или теорема Куратовского, — теорема в теории графов, дающая необходимое и достаточное условие планарности графа. Имеет эквивалентаную формулировку на языке миноров, так называемою теорему Вагнера.

Теорема утверждает, что графы K5 (полный граф на 5 вершинах) и K3,3 (полный двудольный граф имеющий по 3 вершины в каждой доле) являются единственными минимальными непланарными графами.

История[править | править код]

Была доказана в 1930 году польским математиком Казимиром Куратовским[1] и в 1927 году советским математиком Львом Семёновичем Понтрягиным, который не опубликовал своё доказательство.

Предварительные определения[править | править код]

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

Граф называется подразбиением графа если можно получить из добавлением вершин на его рёбра.

Формулировка[править | править код]

Граф планарен тогда и только тогда, когда он не содержит подразбиениий полного графа с пятью вершинами (K5) и полного двудольного графа с тремя вершинами в каждой доле (K3,3).

Доказательство[править | править код]

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

Достаточность в теореме Куратовского доказывается индукцией по количеству ребер в графе. Шаг индукции следует из Утверждения, поскольку если или или или для некоторого ребра e графа , то или . ‘Для ’ утверждение очевидно. Если , то , а если , то или .

Утверждение[править | править код]

Если связный граф не изоморфен ни , ни , и для любого ребра графа оба графа и планарны, то планарен.

Лемма о графах Куратовского[править | править код]

Для произвольного графа следующие три условия равносильны:

  1. Для любого ребра xy графа граф не содержит θ-графа, и из каждой вершины графа выходит не менее двух ребер.
  2. Для любого ребра xy графа граф является циклом (содержащим вершин).
  3. изоморфен или .

Доказательство утверждения[править | править код]

Так как не изоморфен ни , ни , то по лемме о графах Куратовского существует ребро графа , для которого в графе найдется либо вершина степени меньше 2 (в ), либо θ-подграф.

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

Поэтому в графе нет изолированных вершин, и если есть висячая вершина p, то она соединена и с x, и с y в графе . Нарисуем граф на плоскости без самопересечений. Так как в графе из p выходит три ребра, то 'с одной стороны' от пути xpy из p не выходит ребер. 'Подрисуем' ребро xy вдоль пути xpy 'с этой стороны' от него. Получим изображение графа G на плоскости без самопересечений.

Рассмотрим теперь случай, когда в графе найдется θ-подграф.

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

Нарисуем без самопересечений на плоскости граф . Изображение графа на плоскости получается стиранием ребер графа , выходящих из вершины xy. Обозначим через границу той грани (изображения) графа , которая содержит вершину xy графа .

Заметим, что граница грани не может содержать θ-подграфа.

(Это утверждение можно вывести из теоремы Жордана. Другое доказательство получается от противного: если граница грани содержит θ-подграф, то возьмем точку внутри этой грани и соединим ее тремя ребрами с тремя точками на трех 'дугах' θ-подграфа. Получим изображение графа на плоскости без самопересечений. Противоречие.)

Поэтому . Тогда ребра графа находятся в грани (изображения) графа , не содержащей вершины xy. Значит, граф разбивает плоскость. Поэтому найдется цикл , относительно которого вершина xy лежит (не уменьшая общности) внутри, а некоторое ребро графа — вне.

Обозначим через объединение всех ребер графа , лежащих вне цикла . (Возможно,.) Можно считать, что — подграф в (а не только в ).

Граф можно нарисовать на плоскости без самопересечений. Можно считать, что ребра графа G, выходящие из x или y, на изображении графа лежат внутри цикла .

Каждая компонента связности графа пересекается с не более чем по одной точке.

(Если это не так, то в есть путь, соединяющий две точки на . На изображении графа соответствующий путь лежит внутри цикла . Значит, этот путь разбивает внутреннюю часть цикла на две части, одна из которых содержит xy, a другая не лежит в грани, ограниченной . Поэтому — противоречие.)

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

Вариации и обобщения[править | править код]

Примечания[править | править код]

Ссылки[править | править код]