1632
правки
Изменения
м
rollbackEdits.php mass rollback
Теорему доказал в 1927 году известный советский математик Лев Семенович Понтрягин, но не опубликовал. <br>Независимо от Понтрягина в 1930 году доказательста нашел и впервые напечатал польский математик Казимир Куратовский. <br>Первые доказательства теоремы Понтрягина - Куратовского были очень сложными. Сравнительно простое доказательство нашел в 1997 г. петербургский школьник Юрий Макарычев. <br>
<br>
|proof =
Заметим, что из планарности графа следует планарность гомеоморфного графа и наоборот. В самом деле, пусть <tex> G_1 </tex> {{---}} плоский граф.
Если добавить на нужных ребрах вершины степени <tex> 2 </tex> и удалить некотрые вершины степени <tex> 2 </tex> в <tex> G_1 </tex>, получим укладку гомеоморфного графа <tex> G_2 </tex>. Таким образом, доказательство достаточности необходимости следует из [[Непланарность_K5_и_K3,3| непланарности <tex>K_5</tex> и <tex>K_{3, 3}</tex>]].
Докажем неоходимостьдостаточность. От противного: пусть существует непланарный граф, который не содержит подграфов, гомеоморфных <tex> K_{5} </tex> или <tex> K_{3, 3} </tex>. Пусть <tex> G </tex> {{---}} такой граф с наименьшим возможным числом рёбер, не содержащий изолированных вершин.
=== G связен ===
Если <tex> G </tex> не [[Отношение_связности,_компоненты_связности|связен]], то в силу минимальности <tex> G </tex> его компоненты связности планарны и, следовательно, сам граф <tex> G </tex> планарен.
Ввиду леммы 1 будем говорить, что любая внешняя часть является <b><tex>(a,b)</tex> {{---}} разделяющей частью</b> (англ. ''separating part''), поскольку она встречает и <tex>C(a,b)</tex>, и <tex>C(b,a)</tex>.
}}
Аналогично можно ввести понятие <tex>(a,b)</tex> {{---}} разделяющей внутренней части. Заметим, что внутрення внутренняя часть может встречать цикл <tex>C</tex>, вообще говоря, более чем в двух точках, но не менее чем в двух точках.
{{Лемма
|about=2
|proof =
Пусть, от противного, лемма 3 неверна. Упорядочим <tex>(a,b)</tex> {{---}} разделяющие внутренние части в порядке их прикрепления к циклу <tex>C</tex> при движении по циклу от <tex>a</tex> до <tex>b</tex> и обозначим их соответственно через <tex>In_{1},In_{2},...\dots</tex> Пусть <tex>u_{1}</tex> и <tex>u_{2}</tex> {{---}} первая и последняя вершины из <tex>C(a,b)</tex>, в которых <tex>In_{1}</tex> встречает цикл <tex>C</tex>, а <tex>v_{1}</tex> и <tex>v_{2}</tex> {{---}} первая и последняя вершины из <tex>C(b,a)</tex>, в которых <tex>In_{1}</tex> встречает цикл <tex>C</tex> (возможно, вообще говоря, <tex>u_{1} = u_{2}</tex> или <tex>v_{1} = v_{2}</tex>). Поскольку лемма 3 неверна, для любой внешней части обе её вершины, в которых она встречает <tex>C</tex>, лежат либо на <tex>C[v_{2},u_{1}]</tex>, либо на <tex>C[u_{2},v_{1}]</tex>. Тогда снаружи цикла <tex>C</tex> можно провести жорданову кривую <tex>P</tex>, не пересекая рёбер графа <tex>G'</tex>, соединяющую <tex>v_{2}</tex> с <tex>u_{1}</tex>.
[[Файл:nb.pic.12.png|310px|рис. 12]]
==Источники информации==
* [https://ru.wikipedia.org/wiki/Планарный_граф Википедия {{---}} Планарный граф]
* [http://en.wikipedia.org/wiki/Kuratowski's_theorem Wikipedia {{---}} Kuratowski's_theorems theorem]
* [http://acm.math.spbu.ru/~sk1/download/books/TheoremKuratowski.pdf "Вокруг критерия Куратовского планарности графов" (стр. 118)]
* Асанов М., Баранский В., Расин В. {{---}} Дискретная математика {{---}} Графы, матроиды, алгоритмы
