Теорема Понтрягина-Куратовского — различия между версиями
м |
(Перерисованы картинки 1-3) |
||
Строка 20: | Строка 20: | ||
=== G {{---}} [[Отношение_вершинной_двусвязности|блок]] === | === G {{---}} [[Отношение_вершинной_двусвязности|блок]] === | ||
Пусть, от противного, в графе есть [[Точка_сочленения,_эквивалентные_определения|точка сочленения]] <tex> v </tex>. Через <tex> G_1 </tex> обозначим подграф графа <tex> G </tex>, порождённый вершинами одной из компонент связности графа <tex> G - v</tex> и вершинной <tex> v </tex>, а через | Пусть, от противного, в графе есть [[Точка_сочленения,_эквивалентные_определения|точка сочленения]] <tex> v </tex>. Через <tex> G_1 </tex> обозначим подграф графа <tex> G </tex>, порождённый вершинами одной из компонент связности графа <tex> G - v</tex> и вершинной <tex> v </tex>, а через | ||
− | <tex> G_2 </tex> подграф графа <tex> G </tex>, порождённый вершинами остальных компонент связности графа <tex> G - v </tex> и вершиной <tex> v </tex>. | + | <tex> G_2 </tex> подграф графа <tex> G </tex>, порождённый вершинами остальных компонент связности графа <tex> G - v </tex> и вершиной <tex> v </tex>. |
В силу минимальности <tex> G </tex>, <tex> G_1 </tex> и <tex> G_2 </tex> {{---}} планарны. | В силу минимальности <tex> G </tex>, <tex> G_1 </tex> и <tex> G_2 </tex> {{---}} планарны. | ||
− | [[Файл:New. | + | |
+ | [[Файл:New.nb.pic.1.png|400px|рис. 1]] | ||
+ | |||
Возьмём укладку графа <tex> G_1 </tex> на плоскости такую, что вершина <tex> v </tex> лежит на границе внешней грани. Ее можно получить, взяв любую укладку <tex> G_1 </tex> на плоскости, по ней построив укладку на шаре, используя обратную стереографическую проекцию<ref> [http://en.wikipedia.org/wiki/Stereographic_projection Wikipedia {{---}} Stereographic projection] </ref>, потом повернуть сферу так, чтоб <tex> v </tex> оказалась на внешней грани стереографической проекции повернутого шара. | Возьмём укладку графа <tex> G_1 </tex> на плоскости такую, что вершина <tex> v </tex> лежит на границе внешней грани. Ее можно получить, взяв любую укладку <tex> G_1 </tex> на плоскости, по ней построив укладку на шаре, используя обратную стереографическую проекцию<ref> [http://en.wikipedia.org/wiki/Stereographic_projection Wikipedia {{---}} Stereographic projection] </ref>, потом повернуть сферу так, чтоб <tex> v </tex> оказалась на внешней грани стереографической проекции повернутого шара. | ||
− | Затем во внешней грани графа <tex> G_1 </tex> возьмём укладку графа <tex> G_2 </tex> такую, что вершина <tex> v </tex> будет представлена на плоскости в двух экземплярах. | + | Затем во внешней грани графа <tex> G_1 </tex> возьмём укладку графа <tex> G_2 </tex> такую, что вершина <tex> v </tex> будет представлена на плоскости в двух экземплярах. |
− | [[Файл: | + | |
− | Соединим два экземпляра вершины <tex> v </tex> пучком жордановых линий, не допуская лишних пересечений с укладками графов <tex> G_1 </tex> и <tex> G_2 </tex>, состоящим из такого количества линий, какова степень вершины <tex> v </tex> в графе <tex> G_2 </tex>. Далее отбросим вхождение вершины <tex> v </tex> в граф <tex> G_2 </tex>, заменяя инцидентные ей рёбра на жордановы линии, полученные из линий указанного пучка и рёбер | + | [[Файл:nb.pic.2.png|400px|рис. 2]] |
− | [[Файл: | + | |
+ | Соединим два экземпляра вершины <tex> v </tex> пучком жордановых линий, не допуская лишних пересечений с укладками графов <tex> G_1 </tex> и <tex> G_2 </tex>, состоящим из такого количества линий, какова степень вершины <tex> v </tex> в графе <tex> G_2 </tex>. Далее отбросим вхождение вершины <tex> v </tex> в граф <tex> G_2 </tex>, заменяя инцидентные ей рёбра на жордановы линии, полученные из линий указанного пучка и рёбер. | ||
+ | |||
+ | [[Файл:nb.pic.3.png|400px|рис. 3]] | ||
+ | |||
Таким образом мы получили укладку графа <tex> G </tex> на плоскости, что невозможно. | Таким образом мы получили укладку графа <tex> G </tex> на плоскости, что невозможно. | ||
=== В G нет мостов === | === В G нет мостов === |
Версия 14:57, 16 декабря 2014
Теорему доказал в 1927 году известный советский математик Лев Семенович Понтрягин, но не опубликовал.
Независимо от Понтрягина в 1930 году доказательста нашел и впервые напечатал польский математик Казимир Куратовский.
Первые доказательства теоремы Понтрягина - Куратовского были очень сложными. Сравнительно простое доказательство нашел в 1997 г. петербургский школьник Юрий Макарычев.
Содержание
- 1 G связен
- 2 G — обыкновенный граф
- 3 G — блок
- 4 В G нет мостов
- 5 В G' существует цикл, содержащий вершины a и b
- 6 Вспомогательные определения и утверждение об одновременно разделяющейся внутренней части
- 7 Разбор случаев взаимного положения вершин a, b, c, d, u1, u2, v1, v2
- 8 См. также
- 9 Примечания
- 10 Источники информации
Теорема: | ||||||||||||||||||||||||||||||||
Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных или . | ||||||||||||||||||||||||||||||||
Доказательство: | ||||||||||||||||||||||||||||||||
Заметим, что из планарности графа следует планарность гомеоморфного графа и наоборот. В самом деле, пусть непланарности . и — плоский граф. Если добавить на нужных ребрах вершины степени и удалить некотрые вершины степени в , получим укладку гомеоморфного графа . Таким образом, доказательство достаточности следует изДокажем неоходимость. От противного: пусть существует непланарный граф, который не содержит подграфов, гомеоморфных или . Пусть — такой граф с наименьшим возможным числом рёбер, не содержащий изолированных вершин.G связенЕсли связен, то в силу минимальности его компоненты связности планарны и, следовательно, сам граф планарен. неG — обыкновенный графВ самом деле, пусть в графе есть петля или кратное ребро . Тогда в силу минимальности граф планарен. Добавляя ребро к графу получим, что граф планарен.G — блокПусть, от противного, в графе есть точка сочленения . Через обозначим подграф графа , порождённый вершинами одной из компонент связности графа и вершинной , а через подграф графа , порождённый вершинами остальных компонент связности графа и вершиной . В силу минимальности , и — планарны.Возьмём укладку графа [1], потом повернуть сферу так, чтоб оказалась на внешней грани стереографической проекции повернутого шара. на плоскости такую, что вершина лежит на границе внешней грани. Ее можно получить, взяв любую укладку на плоскости, по ней построив укладку на шаре, используя обратную стереографическую проекциюЗатем во внешней грани графа возьмём укладку графа такую, что вершина будет представлена на плоскости в двух экземплярах.Соединим два экземпляра вершины пучком жордановых линий, не допуская лишних пересечений с укладками графов и , состоящим из такого количества линий, какова степень вершины в графе . Далее отбросим вхождение вершины в граф , заменяя инцидентные ей рёбра на жордановы линии, полученные из линий указанного пучка и рёбер.Таким образом мы получили укладку графа на плоскости, что невозможно.В G нет мостовГраф мостов. не равен и в нем нет точек сочленения, следовательно в нетВ G' существует цикл, содержащий вершины a и bПусть — произвольное ребро графа , .
Пусть и лежат в одном блоке графа .
Заметим, что в графе Отметим, что опять вершина представлена на плоскости в двух экземплярах. Очевидно, добавление ребра не меняет планарности графа . Склеим оба вхождения вершины точно так же, как это мы сделали в предыдущем пункте доказательства (рис. 6).Сотрем затем ранее добавленные ребра и . В результате мы получим укладку графа на плоскости, что невозможно. Утверждение доказано.Вспомогательные определения и утверждение об одновременно разделяющейся внутренней частиСреди всех укладок графа на плоскости и среди всех циклов , содержащих и , зафиксируем такую укладку и такой цикл, что внутри области, ограниченной циклом , лежит максимальное возможное число граней графа . Зафиксируем один из обходов по циклу (на рисунках будем рассматривать обход по часовой стрелке по циклу ). Для вершин и цикла через будем обозначать простую — цепь, идущую по циклу от до в направлении обхода цикла. Конечно, . Положим { }, т.е. получено из отбрасыванием вершин и .
В силу связности графа для любой внешней компоненты должны существовать рёбра в , соединяющие её с вершинами цикла .
В силу связности графа для любой внутренней компоненты должны существовать рёбра в , соединяющие её с вершинами цикла .
Будем говорить, что внешняя (внутренняя) часть встречает цикл в своих точках прикрепления к циклу .
Аналогично можно ввести понятие — разделяющей внутренней части. Заметим, что внутрення часть может встречать цикл , вообще говоря, более чем в двух точках, но не менее чем в двух точках.
Разбор случаев взаимного положения вершин a, b, c, d, u1, u2, v1, v2
| ||||||||||||||||||||||||||||||||
См. также
Примечания
Источники информации
- Википедия — Планарный граф
- Wikipedia — Kuratowski's_theorem
- "Вокруг критерия Куратовского планарности графов" (стр. 118)
- Асанов М., Баранский В., Расин В. — Дискретная математика — Графы, матроиды, алгоритмы