Войти
Подразделение K 3,3 в обобщенном графе Петерсена G (9,2), показывающее, что граф непланарен. В теории графов, теорема Куратовская является математической запрещались графы характеризация из плоских графов, названных в честь Куратовского. Она утверждает, что конечный граф является планарным тогда и только тогда, когда он не содержит подграф, который является подразделением из K 5 (далее полный граф на пять вершин ) или из K 3,3 ( полного двудольного графа на шесть вершин, три из которых соединяются с каждым из трех других, также называемых графом полезности ).
Плоский граф представляет собой график, вершины которого могут быть представлены точками в евклидовой плоскости, а ребра могут быть представлены простыми кривыми в одной и той же плоскости, соединяющих точки, представляющих их конечные точки, такие, что никакие две кривые не пересекаются, кроме общей конечной точке. Плоские графы часто рисуются с отрезками прямых линий, представляющими их ребра, но по теореме Фари это не имеет значения для их теоретико-графовой характеристики.
Подразделение графа представляет собой график, образованный подразделяя ее края в дорожек одного или нескольких ребер. Теорема утверждает Куратовским, что конечный граф G является планарным, если это не представляется возможным разделить края K 5 или K 3,3, а затем, возможно, добавить дополнительные ребра и вершины, чтобы сформировать граф, изоморфные к G. Эквивалентно, конечный граф является планарным тогда и только тогда, когда он не содержит подграфа, которое гомеоморфно на K 5 или K 3,3.
Доказательство без слов, что тессеракт графа является неплоским использованием Куратовских или теорем Вагнера и нахождения либо К 5 (вверху) или К 3,3 (внизу) подграфам Если G представляет собой график, который содержит подграф H, который является подразделением K 5 или K 3,3, то Н известен как Куратовскому подграфа из G. В этих обозначениях теорема Куратовского может быть выражена лаконично: граф является плоским тогда и только тогда, когда он не имеет подграфа Куратовского.
Два графа K 5 и K 3,3 непланарны, что может быть показано либо анализом случая, либо аргументом с использованием формулы Эйлера. Кроме того, подразделяя график не может превратить непланарный граф в планарном граф: если разбиение графа G имеет плоский чертеж, путь кривых образует подразделение, которые могут быть использованы для представления краев G самых. Следовательно, граф, содержащий подграф Куратовского, не может быть плоским. Более сложное направление в доказательстве теоремы Куратовского - показать, что, если граф непланарный, он должен содержать подграф Куратовского.
Подграф Куратовского неплоского графа может быть найден за линейное время, измеряемое размером входного графа. Это позволяет проверить правильность алгоритма проверки планарности для неплоских входных данных, поскольку легко проверить, является ли данный подграф подграфом Куратовского. Обычно неплоские графы содержат большое количество подграфов Куратовского. Извлечение этих подграфов необходимо, например, в алгоритмах ветвей и отсечений для минимизации пересечений. Можно выделить большое количество подграфов Куратовского во времени в зависимости от их общего размера.
Казимеж Куратовски опубликовал свою теорему в 1930 году. Теорема была независимо доказана Оррином Фринком и Полом Смитом также в 1930 году, но их доказательство так и не было опубликовано. Частный случай кубических плоских графов (для которых единственный минимальный запрещенный подграф - K 3,3) был также независимо доказан Карлом Менгером в 1930 году. С тех пор было обнаружено несколько новых доказательств теоремы.
В Советском Союзе теорема Куратовского была известна либо как теорема Понтрягина – Куратовского, либо как теорема Куратовского – Понтрягина, поскольку теорема, как сообщается, была независимо доказана Львом Понтрягиным около 1927 года. Однако, поскольку Понтрягин никогда не публиковал свое доказательство, это использование не получило распространения в другие места.
Тесно связанный результат, теорема Вагнера, характеризует плоские графы их минорами в терминах тех же двух запрещенных графов K 5 и K 3,3. Каждый подграф Куратовского является частным случаем минора одного и того же типа, и хотя обратное неверно, нетрудно найти подграф Куратовского (того или иного типа) из одного из этих двух запрещенных миноров; следовательно, эти две теоремы эквивалентны.
Расширением является теорема Робертсона-Сеймура.
