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

По поводу теоремы о точечной топологии см. Проблема Куратовского о замыкании-дополнении.
Подразделение K3,3 в обобщенный граф Петерсена грамм(9,2), показывающее, что граф неплоский.

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

Заявление

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

А подразделение графа - это граф, образованный разделением его ребер на пути одного или нескольких ребер. Теорема Куратовского утверждает, что конечный граф грамм является плоским, если невозможно разделить края K5 или же K3,3, а затем, возможно, добавить дополнительные ребра и вершины, чтобы сформировать граф изоморфный к грамм. Эквивалентно конечный граф является плоским тогда и только тогда, когда он не содержит подграф, который гомеоморфный к K5 или же K3,3.

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

Если грамм - граф, содержащий подграф ЧАС это подразделение K5 или же K3,3, тогда ЧАС известен как Подграф Куратовского из грамм.[1] В этих обозначениях теорема Куратовского может быть выражена лаконично: граф является плоским тогда и только тогда, когда он не имеет подграфа Куратовского.

Два графика K5 и K3,3 неплоские, что может быть показано либо анализ случая или аргумент с участием Формула Эйлера. Кроме того, подразделение графа не может превратить непланарный граф в планарный: если подразделение графа грамм имеет планарный чертеж, пути кривых формы подразделения, которые могут использоваться для представления краев грамм сам. Следовательно, граф, содержащий подграф Куратовского, не может быть плоским. Более сложное направление в доказательстве теоремы Куратовского - показать, что, если граф непланарный, он должен содержать подграф Куратовского.

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

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

История

Казимеж Куратовски опубликовал свою теорему в 1930 году.[5] Теорема была независимо доказана Оррин Фринк и Пол Смит, также в 1930 г.,[6] но их доказательство так и не было опубликовано. Частный случай кубический планарные графы (для которых единственный минимальный запрещенный подграф K3,3) также независимо доказано Карл Менгер в 1930 г.[7]С тех пор было обнаружено несколько новых доказательств теоремы.[8]

в Советский союз, Теорема Куратовского была известна как Теорема Понтрягина – Куратовского. или Теорема Куратовского – Понтрягина.,[9]поскольку теорема была независимо доказана Лев Понтрягин около 1927 г.[10]Однако, поскольку Понтрягин никогда не публиковал свое доказательство, это использование не распространилось на другие места.[11]

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

Тесно связанный результат, Теорема Вагнера, характеризует планарные графы их несовершеннолетние в терминах тех же двух запрещенных графов K5 и K3,3. Каждый подграф Куратовского является частным случаем минора того же типа, и хотя обратное неверно, нетрудно найти подграф Куратовского (того или иного типа) из одного из этих двух запрещенных миноров; следовательно, эти две теоремы эквивалентны.[12]

Расширение - это Теорема Робертсона-Сеймура.

Смотрите также

Рекомендации

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