Введение

Теорема о запрещённых подграфах в планарных графах, теорема о топологии точечных множеств.

В теории графов теорема Куратовского — это математическая характеристика планарных графов через запрещённые графы, названная в честь Казимежа Куратовского. Она утверждает, что конечный граф является планарным тогда и только тогда, когда он не содержит подграф, являющийся подразделением полного графа на пять вершин (K₅) или полного двудольного графа на шесть вершин, в котором три вершины соединены со всеми тремя вершинами другой доли (K₃,₃), также известного как граф полезности.

Заявление

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

Субграфы Куратовского

Если граф содержит подграф, являющийся подразделением графа K₅ или K₃,₃, то он называется подграфом Куратовского для данного графа. Используя это обозначение, теорему Куратовского можно кратко сформулировать так: граф планарный тогда и только тогда, когда он не содержит подграфа Куратовского. Графы K₅ и K₃,₃ непланарны, что можно показать либо анализом случаев, либо аргументом, основанным на формуле Эйлера. Кроме того, подразделение графа не может превратить непланарный граф в планарный: если подразделение графа имеет планарное изображение, то пути этого подразделения образуют кривые, которые можно использовать для представления рёбер исходного графа. Следовательно, граф, содержащий подграф Куратовского, не может быть планарным. Более сложной частью доказательства теоремы Куратовского является то, что если граф непланарный, то он должен содержать подграф Куратовского.

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

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

Сопутствующие результаты

Тесно связанный результат, теорема Вагнера, характеризует планарные графы по их минорам, используя те же два запрещенных графа. Любой подграф Куратовского является частным случаем минора того же типа, и хотя обратное неверно, несложно найти подграф Куратовского (одного из двух типов) из одного из этих двух запрещенных миноров; следовательно, эти две теоремы эквивалентны. Обобщением является теорема Робертсона — Сеймура.