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

О запрещенных подграфах в планарных графах

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

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

Заявление

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

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

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

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

Если — граф, содержащий подграф , являющийся подразделением или , то называется подграфом Куратовского графа . ^[1] С помощью этой записи теорему Куратовского можно выразить кратко: граф является планарным тогда и только тогда, когда он не имеет подграфа Куратовского. ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle K_{5}}$ ${\displaystyle K_{3,3}}$ ${\displaystyle H}$ ${\displaystyle G}$

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

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

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

История

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

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

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

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

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

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

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

Ссылки

1. Tutte, WT (1963), «Как нарисовать график», Труды Лондонского математического общества , Третья серия, 13 : 743–767, doi :10.1112/plms/s3-13.1.743, MR  0158387.
2. Уильямсон, С.Г. (сентябрь 1984 г.), «Поиск в глубину и подграфы Куратовского», J. ACM , 31 (4): 681–693, doi : 10.1145/1634.322451 , S2CID  8348222.
3. Мельхорн, Курт ; Наэр, Стефан (1999), LEDA: Платформа для комбинаторных и геометрических вычислений, Cambridge University Press, стр. 510, ISBN 9780521563291.
4. Чимани, Маркус; Мютцель, Петра ; Шмидт, Йенс М. (2007), «Эффективное извлечение множественных подразделений Куратовского», в Хонг, Сок-Хи ; Нишизеки, Такао ; Куан, Ву (ред.), Рисование графов: 15-й международный симпозиум, GD 2007, Сидней, Австралия, 24-26 сентября 2007 г., пересмотренные статьи , заметки лекций по информатике , т. 4875, Springer, стр. 159–170, doi : 10.1007/978-3-540-77537-9_17 , ISBN 978-3-540-77536-2
5. Куратовский, Казимеж (1930), «Sur le problème des courbes gauches en topologie» (PDF) , Fund. Математика. (на французском языке), 15 : 271–283, doi : 10.4064/fm-15-1-271-283.
6. Фринк, Оррин ; Смит, Пол А. (1930), «Неприводимые непланарные графы», Бюллетень AMS , 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, doi : 10.1002/jgt.3190050304, MR  0625064.
9. Бурштейн, Майкл (1978), «Теорема Куратовского-Понтрягина о планарных графах», Журнал комбинаторной теории, Серия B , 24 (2): 228–232, doi :10.1016/0095-8956(78)90024-2
10. Кеннеди, Джон У.; Квинтас, Луис В.; Сысло, Мачей М. (1985), «Теорема о планарных графах», Historia Mathematica , 12 (4): 356–368, doi : 10.1016/0315-0860(85)90045-X
11. Чартран, Гэри ; Лесняк, Линда; Чжан, Пин (2010), Графики и орграфы (5-е изд.), CRC Press, стр. 237, ISBN 9781439826270.
12. Бонди, JA ; Мурти, USR (2008), Теория графов, Graduate Texts in Mathematics, т. 244, Springer, стр. 269, ISBN 9781846289699.