В теории графов , теорема Куратовская является математической запрещались графы характеризация из плоских графов , названных в честь Куратовского . Она утверждает , что конечный граф является планарным тогда и только тогда , когда он не содержит подграф , который является подразделением из K 5 (далее полный граф на пять вершин ) или из K 3,3 ( полного двудольного графа на шесть вершин, три из которых соединяются с каждым из трех других, также называемых графом полезности ).
Заявление
Плоский граф представляет собой график, вершины которого могут быть представлены точками в евклидовой плоскости , а ребра могут быть представлены простыми кривыми в одной и той же плоскости , соединяющих точки , представляющих их конечные точки, такие , что никакие две кривые не пересекаются , кроме общей конечной точке. Плоские графы часто рисуются с отрезками прямых линий, представляющими их ребра, но по теореме Фари это не имеет значения для их теоретико-графовой характеристики.
Подразделение графа представляет собой график , образованный подразделяя ее края в дорожек одного или нескольких ребер. Теорема утверждает Куратовским, что конечный граф G является планарным , если это не представляется возможным разделить края K 5 или K 3,3 , а затем , возможно , добавить дополнительные ребра и вершины, чтобы сформировать граф , изоморфные к G . Эквивалентно, конечный граф является планарным тогда и только тогда , когда он не содержит подграфа, которое гомеоморфно на K 5 или K 3,3 .
Подграфы Куратовского
Если G представляет собой график , который содержит подграф H , который является подразделением K 5 или K 3,3 , то Н известен как Куратовскому подграфа из G . [1] В этих обозначениях теорема Куратовского может быть выражена лаконично: граф является плоским тогда и только тогда, когда он не имеет подграфа Куратовского.
Два графа K 5 и K 3,3 непланарны, что может быть показано либо анализом случая, либо аргументом с использованием формулы Эйлера . Кроме того, подразделяя график не может превратить непланарный граф в планарном граф: если разбиение графа G имеет плоский чертеж, путь кривых образует подразделение , которые могут быть использованы для представления краев G самых. Следовательно, граф, содержащий подграф Куратовского, не может быть плоским. Более сложное направление в доказательстве теоремы Куратовского - показать, что, если граф непланарный, он должен содержать подграф Куратовского.
Алгоритмические последствия
Подграф Куратовского неплоского графа может быть найден за линейное время , измеряемое размером входного графа. [2] Это позволяет проверить правильность алгоритма проверки планарности для неплоских входных данных, поскольку легко проверить, является ли данный подграф подграфом Куратовского. [3] Обычно неплоские графы содержат большое количество подграфов Куратовского. Извлечение этих подграфов необходимо, например, в алгоритмах ветвей и отсечений для минимизации пересечений. Можно выделить большое количество подграфов Куратовского во времени в зависимости от их общего размера. [4]
История
Казимеж Куратовски опубликовал свою теорему в 1930 году. [5] Теорема была независимо доказана Оррином Фринком и Полом Смитом также в 1930 году [6], но их доказательство так и не было опубликовано. Частный случай кубических плоских графов (для которых единственный минимальный запрещенный подграф - K 3,3 ) был также независимо доказан Карлом Менгером в 1930 году. [7] С тех пор было обнаружено несколько новых доказательств теоремы. [8]
В Советском Союзе , теорема Куратовского была известна либо как теорема Понтрягина-Куратовского или теоремы Куратовского-Понтрягина , [9] , как теорема сообщается независимо доказана Понтрягин около 1927. [10 не] Однако, как Понтрягина не опубликовал его доказательство , это использование не распространилось на другие места. [11]
Связанные результаты
Тесно связанный результат, теорема Вагнера , характеризует плоские графы их минорами в терминах тех же двух запрещенных графов K 5 и K 3,3 . Каждый подграф Куратовского является частным случаем минора одного и того же типа, и хотя обратное неверно, нетрудно найти подграф Куратовского (того или иного типа) из одного из этих двух запрещенных миноров; следовательно, эти две теоремы эквивалентны. [12]
Расширением является теорема Робертсона-Сеймура .
Смотрите также
- Гипотеза Кельмана – Сеймура о том , что 5-связные неплоские графы содержат подразделение K 5
Рекомендации
- ^ Tutte, WT (1963), "Как нарисовать график", Труды Лондонского математического общества , Третья серия, 13 : 743-767, DOI : 10.1112 / ПНИЛ / s3-13.1.743 , MR 0158387.
- ^ Williamson, SG (сентябрь 1984), "поиск в глубине и Куратовские подграфы", J. ACM , 31 (4): 681-693, DOI : 10,1145 / +1634,322451.
- ^ Мельхорн, Курт ; Нахер, Стефан (1999), LEDA: платформа для комбинаторных и геометрических вычислений , Cambridge University Press, стр. 510, ISBN 9780521563291.
- ^ Чимани, Маркус; Муцель, Петра ; Шмидт, Йенс М. (2007), Эффективное извлечение множества подразделений Куратовски , стр. 159–170, DOI : 10.1007 / 978-3-540-77537-9_17 Неизвестный параметр
|conference=
игнорируется ( справка ) . - ^ Куратовски, Казимеж (1930), "Sur le problème des Courbes gauches en topologie" (PDF) , Fund. Математика. (на французском языке), 15 : 271–283.
- ^ Фринк, Оррин ; Смит, Пол А. (1930), "Неприводимые неплоские графы", Бюллетень AMS , 36 : 214
- ^ Менгер, Карл (1930), "Über plättbare Dreiergraphen und Potenzen nichtplättbarer Graphen", Anzeiger der Akademie der Wissenschaften в Вене , 67 : 85–86
- ^ Thomassen, Карстен (1981), "теорема Куратовской", Журнал теории графов , 5 (3): 225-241, DOI : 10.1002 / jgt.3190050304 , MR 0625064.
- ^ Бурштейн, Майкл (1978), «Теорема Куратовского-Понтрягина о плоских графах», Журнал комбинаторной теории, серия B , 24 : 228–232, DOI : 10.1016 / 0095-8956 (78) 90024-2
- ^ Кеннеди, Джон В .; Quintas, Луи V .; Sysło, Маца М. (1985), "теорема о плоских графах", Хистория Mathematica , 12 : 356-368, DOI : 10.1016 / 0315-0860 (85) 90045-X
- ^ Чартран, Гэри ; Лесняк, Линда; Чжан, Пинг (2010), Графы и диграфы (5-е изд.), CRC Press, стр. 237, ISBN 9781439826270.
- ^ Бонди, JA ; Мурти, USR (2008), Теория графов , Тексты для выпускников по математике, 244 , Springer, стр. 269, ISBN 9781846289699.