Теорема Куратовского

Теорему о топологии множества точек см. в задаче Куратовского о замыкании и дополнении .

Подразделение K _3,3 в обобщенном графе Петерсена G (9,2), показывающее, что граф непланарен.

В теории графов теорема Куратовского представляет собой математическую характеристику запрещенных графов плоских графов , названную в честь Казимира Куратовского . Он утверждает, что конечный граф является плоским тогда и только тогда, когда он не содержит подграфа , являющегося подразделением графа. $K_{5}$ ( полный граф на пяти вершинах ) или $K_{3,3}$ ( полный двудольный граф на шести вершинах, три из которых соединяются друг с другом с тремя другими, также известный как граф полезности ).

Заявление

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

Подразделение пути графа — это граф, образованный разделением его ребер на из одного или нескольких ребер. Теорема Куратовского утверждает, что конечный граф $G$ является плоским, если невозможно разделить ребра $K_{5}$ или $K_{3,3}$, а затем, возможно, добавить дополнительные ребра и вершины, чтобы сформировать граф изоморфный , $G$. Эквивалентно, конечный граф является плоским тогда и только тогда, когда он не содержит подграфа гомеоморфного , $K_{5}$ или $K_{3,3}$.

Подграфы Куратовского

Доказательство без слов того, что граф гиперкуба неплоский , с использованием теорем Куратовского или Вагнера и нахождением либо K ₅ (вверху), либо K _3,3 (внизу) подграфов.

Если $G$ это граф, содержащий подграф $H$ это подразделение $K_{5}$ или $K_{3,3}$, затем $H$ известен как Куратовского подграф $G$. С помощью этих обозначений теорему Куратовского можно выразить кратко: граф планарен тогда и только тогда, когда он не имеет подграфа Куратовского.

Два графика $K_{5}$ и $K_{3,3}$ непланарны, как может показать либо анализ случая , либо рассуждение с использованием формулы Эйлера . Кроме того, подразделение графа не может превратить непланарный граф в планарный: если подразделение графа $G$ имеет плоский рисунок, пути подразделения образуют кривые, которые можно использовать для обозначения краев $G$ сам. Следовательно, граф, содержащий подграф Куратовского, не может быть плоским. Более сложное направление доказательства теоремы Куратовского — показать, что если граф неплоский, он должен содержать подграф Куратовского.

Алгоритмические последствия

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

История

Казимеж Куратовский опубликовал свою теорию в 1930 году. Теорема была независимо доказана Оррином Фринк и Полом Смитом , также в 1930 году. но их доказательство так и не было опубликовано. Частный случай кубических плоских графов (для которых единственным минимальным запрещенным подграфом является $K_{3,3}$) также было независимо доказано Карлом Менгером в 1930 году. С тех пор было обнаружено несколько новых доказательств теоремы.

В Советском Союзе теорема Куратовского была известна как теорема Понтрягина-Куратовского или теорема Куратовского-Понтрягина . поскольку теорема, как сообщается, была независимо доказана Львом Понтрягиным примерно в 1927 году. Однако, поскольку Понтрягин так и не опубликовал свое доказательство, это употребление не распространилось в других местах.

Связанные результаты

Близкий результат, теорема Вагнера , характеризует плоские графы по их минорам в терминах тех же двух запрещенных графов. $K_{5}$ и $K_{3,3}$. Каждый подграф Куратовского представляет собой частный случай минора одного и того же типа, и хотя обратное неверно, нетрудно найти подграф Куратовского (того или другого типа) из одного из этих двух запрещенных миноров; следовательно, эти две теоремы эквивалентны.

Расширением является теорема Робертсона-Сеймура .

См. также

• Гипотеза Келманса – Сеймура о том, что 5-связные неплоские графы содержат подразделение $K_{5}$