Теорема Понтрягина-Куратовского — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(g)
м (rollbackEdits.php mass rollback)
 
(не показаны 74 промежуточные версии 15 участников)
Строка 1: Строка 1:
==== Разбор случаев взаимного положения <tex>a, b, c, d, u1, u2, v1, v2</tex> ====
+
Теорему доказал в 1927 году известный советский математик Лев Семенович Понтрягин, но не опубликовал.
Рассмотрим 2 случая.
+
Независимо от Понтрягина в 1930 году доказательста нашел и впервые напечатал польский математик Казимир Куратовский.
 +
Первые доказательства теоремы Понтрягина-Куратовского были очень сложными. Сравнительно простое доказательство нашел в 1997 г. петербургский школьник Юрий Макарычев. <br>  
 +
<br>
  
----
+
__TOC__
  
1. Пусть пара вершин <tex>\ v_1  </tex> и <tex>\ v_2  </tex> является <tex>(a, b)</tex>-разделяющей. <br>
+
{{Теорема
Тогда, в частности, <tex>v_2 \ne a</tex> и  <tex> v_1 \ne b</tex>. В этом случае граф G содержит подграф, гомеоморфный <tex>\ K_{3,3}  </tex> (отметим, что в <tex> In </tex> существует простая <tex>(v_1, v_2)</tex>-цепь)(рис. 1).
+
|statement =
 +
Граф [[Укладка_графа_на_плоскости| планарен]] тогда и только тогда, когда он не содержит подграфов, [[Укладка графа на плоскости #def_hmp| гомеоморфных]] <tex> K_{5} </tex> или <tex> K_{3, 3} </tex> .
 +
|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> {{---}} такой граф с наименьшим возможным числом рёбер, не содержащий изолированных вершин.
2. Пусть пара вершин <tex>v_1</tex> и <tex>v_2</tex> не является <tex>(a, b)</tex>-разделяющей. <br>
+
=== G связен ===
Тогда <tex>v_1, v_2</tex> лежат на <tex>C[a, b]</tex> или на <tex>C[b, a]</tex>. Без ограничения общности будет считать, что <tex>v_1</tex> и <tex>v_2</tex> лежат на <tex>C[a, b]</tex>.<br><br>
+
Если <tex> G </tex>  не [[Отношение_связности,_компоненты_связности|связен]], то в силу минимальности <tex> G </tex> его компоненты связности планарны и, следовательно, сам граф <tex> G </tex> планарен.
 +
=== G {{---}} обыкновенный граф ===
 +
В самом деле, пусть в графе <tex> G </tex> есть петля или кратное ребро <tex> e </tex>. Тогда в силу минимальности <tex> G </tex> граф <tex> G - e </tex> планарен. Добавляя ребро <tex> e </tex> к графу <tex> G - e </tex> получим, что граф <tex> G </tex> планарен.
 +
=== G {{---}} [[Отношение_вершинной_двусвязности|блок]] ===
 +
Пусть, от противного, в графе есть  [[Точка_сочленения,_эквивалентные_определения|точка сочленения]] <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>.
  
2.1. Пусть <tex>v_1</tex> и <tex>v_2</tex> лежат на <tex>C(a, b)</tex>, т.е. <tex>v_1 \ne b</tex> и <tex>v_2 \ne a</tex>(рис. 2). <br><br>
+
В силу минимальности <tex> G </tex>, <tex> G_1 </tex> и <tex> G_2 </tex> {{---}} планарны.
  
2.1.1 Пусть <tex>u_2</tex> лежит на <tex>C(d, a)</tex>.<br>
+
[[Файл:New.nb.pic.1.png|400px|рис. 1]]
Тогда в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 3).<br><br>
 
  
2.1.2. Пусть <tex>u_2 = d</tex>.<br>
+
Возьмём укладку графа <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>In</tex> имеется вершина <tex>w</tex> и три простые цепи от <tex>w</tex> соответственно до <tex>d, v_1, v_2</tex>, которые в качестве общей точки имеют только точку <tex>w</tex>. В этом случае в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 4).<br><br>
 
  
2.1.3. Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>.<br>
+
Затем во внешней грани графа <tex> G_1 </tex> возьмём укладку графа <tex> G_2 </tex> такую, что вершина <tex> v </tex> будет представлена на плоскости в двух экземплярах.
Тогда в графе G есть подграф, гомеоморфный <tex>K{3,3}</tex>(рис. 5).<br><br>
 
  
Теперь рассмотрим случаи, когда хотя бы одна из вершин <tex>v_1</tex> и <tex>v_2</tex> не лежит на <tex>С(a, b)</tex>. Без ограничения общности будем считать, что это вершина <tex>v_1</tex>, т.е <tex>v_1 = b</tex>(поскольку  <tex>v_1</tex> лежит на <tex>C[a, b]</tex>).<br><br>
+
[[Файл:nb.pic.2.png|400px|рис. 2]]
  
2.2. Пусть <tex>v_2 \ne a</tex>.<br><br>
+
Соединим два экземпляра вершины <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>, заменяя инцидентные ей рёбра на жордановы линии, полученные из линий указанного пучка и рёбер.
  
2.2.1. Пусть <tex>u_2</tex> лежит на <tex>C(d, a)</tex>.<br>
+
[[Файл:nb.pic.3.png|400px|рис. 3]]
Тогда в графе G есть пограф, гомеоморфный <tex>K_{3,3}</tex>(рис. 6).<br><br>
 
  
2.2.2. Пусть <tex>u_2 = d</tex>.<br>
+
Таким образом мы получили укладку графа <tex> G </tex> на плоскости, что невозможно.
Тогда в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 7).<br><br>
+
=== В G нет мостов  ===
 +
Граф <tex> G </tex> не равен <tex> K_2 </tex> и в нем нет точек сочленения, следовательно в <tex> G </tex> нет [[Мост,_эквивалентные_определения|мостов]].  
 +
=== В G' существует цикл, содержащий вершины a и b  ===
 +
Пусть <tex> e = ab </tex> {{---}} произвольное ребро графа <tex> G </tex>, <tex> G' = G - e </tex>.  
 +
# граф <tex> G' </tex> планарен в силу минимальности графа <tex> G </tex>.
 +
# граф <tex> G' </tex> связен в силу отсутствия в графе <tex> G </tex> мостов.
  
2.2.3. Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>.<br>
+
Пусть <tex> a </tex> и <tex> b </tex> лежат в одном блоке <tex> B </tex> графа <tex> G' </tex>.
Тогда в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 8). <br><br>
+
# Если <tex>|VB| \geqslant 3</tex>, то существует цикл графа G', содержащий вершины <tex> a </tex> и <tex> b </tex>.
 +
# Если <tex> |VB| = 2 </tex>, то в <tex> B </tex> имеется ребро <tex> e' = ab </tex>, но тогда в <tex> G </tex> имеются кратные рёбра <tex> e </tex> и <tex> e' </tex>, что невозможно.
 +
#Если вершины <tex> a </tex> и <tex> b </tex> лежат в разных блоках графа <tex> G' </tex>, что существует точка сочленения <tex> v </tex>, принадлежащая любой простой <tex> (a, b) </tex> {{---}} цепи графа <tex> G' </tex>. Через <tex> G'_1 </tex> обозначим подграф графа <tex> G' </tex>, порождённый вершиной <tex> v </tex> и вершинами компоненты связности графа <tex> G' - v </tex>, содержащей <tex> a </tex>, а через <tex> G'_2 </tex> {{---}} подграф графа <tex> G' </tex>, порождённый вершиной <tex> v </tex> и вершинами остальных компонент связности графа <tEx> G' - v </tex> (в этом множестве лежит вершина <tex> b </tex>). Пусть <tex> G''_1 = G'_1 + e_1 </tex>, где <tex> e_1 = vb </tex> {{---}} новое ребро.
  
2.3. Пусть <tex>v_2 = a</tex>(рис. 9).<br>
+
[[Файл:nb.pic.4.png|400px|рис. 4]]
Рассмотрим теперь пару вершин <tex>u_1</tex> и <tex>u_2</tex>. Будем считать, что <tex>u_1 = c</tex> и <tex>u_2 = d</tex>, поскольку все другие случаи расположения вершин <tex>u_1</tex> и <tex>u_2</tex> так же, как были рассмотрены все случаи расположения <tex>v_1</tex> и <tex>v_2</tex>. Пусть <tex>P_1</tex> и <tex>P_2</tex> -- соответственно кратчайшие простые <tex>(a, b)</tex>-цепь и <tex>(c, d)</tex>-цепь по внутренней части <tex>In</tex>(рис. 10). Заметим, что <tex>P_1</tex> и <tex>P_2</tex> имеют общую точку.<br><br>
 
  
2.3.1. Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют более одной общей точки.<br>
+
Заметим, что в графе <tex> G''_1 </tex> рёбер меньше, чем в графе <tex> G </tex>. Действительно, вместо ребра <tex> e </tex> в <tex> G''_1 </tex> есть ребро <tex> e_1 </tex> и часть рёбер из графа <tex> G </tex> осталась в графе <tex> G''_2 </tex>. Аналогично, в графе <tex> G''_2 </tex> рёбер меньше, чем в графе <tex> G </tex>. <br/>
Тогда в графе G есть подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 11).<br><br>
+
Теперь в силу минимальности графа <tex> G </tex> графы <tex> G''_1 </tex> и <tex> G''_2 </tex> планарны. Возьмем укладку графа <tex> G''_1 </tex> на плоскости такую, что ребро <tex> e_1 = av </tex> лежит на границе внешней грани(ее существование доказывается аналогично существованию такой укладки для вершины графа). Во внешней грани графа <tex> G''_1 </tex> возьмем укладку графа <tex> G''_2 </tex> такую, что ребро <tex> e_2 = vb </tex> лежит па границе внешней грани.
  
2.3.2. Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют точно одну общую точку <tex>w</tex>.<br>
+
[[Файл:nb.pic.5.png|400px|рис. 5]]
Тогда в графе G есть подграф, гомеоморфный <tex>K_5</tex>(рис. 12).<br><br>
 
  
Таким образом, доказано, что в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex> или <tex>K_5</tex>, что противоречит нашему первому предположению.<br>
+
Отметим, что опять вершина <tex> v </tex> представлена на плоскости в двух экземплярах. Очевидно, добавление ребра <tex> e = ab </tex> не меняет планарности графа <tex> G''_1 U G''_2</tex>. Склеим оба вхождения вершины <tex> v </tex> точно так же, как это мы сделали в предыдущем пункте доказательства.
 +
 
 +
[[Файл:nb.pic.6.png|400px|рис. 6]]
 +
 
 +
Сотрем затем ранее добавленные ребра <tex> e_1 </tex> и <tex> e_2 </tex>. В результате мы получим укладку графа <tex> G </tex> на плоскости, что невозможно. Утверждение доказано.
 +
 
 +
===Вспомогательные определения и утверждение об одновременно разделяющейся внутренней части===
 +
Среди всех укладок графа <tex>G'</tex> на плоскости и среди всех циклов <tex>C</tex>, содержащих <tex>a</tex> и <tex>b</tex>, зафиксируем такую укладку и такой цикл, что внутри области, ограниченной циклом <tex>C</tex>, лежит максимальное возможное число граней графа <tex>G'</tex>. Зафиксируем один из обходов по циклу <tex>C</tex> (на рисунках будем рассматривать обход по часовой стрелке по циклу <tex>C</tex>). Для вершин <tex>u</tex> и <tex>v</tex> цикла <tex>C</tex> через <tex>C[u,v]</tex> будем обозначать простую <tex>(u,v)</tex> {{---}} цепь, идущую по циклу <tex>C</tex> от <tex>u</tex> до <tex>v</tex> в направлении обхода цикла. Конечно, <tex>C[u,v] \ne C[v,u]</tex>. Положим <tex>C(u,v) = C[u,v] \setminus</tex> {<tex>u,v</tex>}, т.е. <tex>C(u,v)</tex> получено из <tex>C[u,v]</tex> отбрасыванием вершин <tex>u</tex> и <tex>v</tex>.
 +
{{Определение
 +
|definition =
 +
<b>Внешним графом </b> (англ. ''Outside graph'') (относительно цикла <tex>C</tex>) будем называть подграф графа <tex>G'</tex>, порождённый всеми вершинами графа <tex>G'</tex>, лежащими снаружи от цикла <tex>C</tex>.
 +
}}
 +
{{Определение
 +
|definition =
 +
<b>Внешними компонентами</b> (англ. ''Outside components'') будем называть компоненты связности внешнего графа.
 +
}}
 +
В силу связности графа <tex>G'</tex> для любой внешней компоненты должны существовать рёбра в <tex>G'</tex>, соединяющие её с вершинами цикла <tex>C</tex>.
 +
{{Определение
 +
|definition =
 +
<b>Внешними частями</b> (англ. ''Outside parts'') будем называть внешние компоненты вместе со всеми рёбрами, соединяющими компоненту с вершинами цикла <tex>C</tex>, и инцидентными им вершинами , либо рёбра графа <tex>G'</tex>, лежащие снаружи от цикла <tex>C</tex> и соединяющие две вершины из <tex>C</tex>, вместе с инцидентными такому ребру вершинами.
 +
}}
 +
[[Файл:nb.pic.7.png|440px|рис. 7]]
 +
{{Определение
 +
|definition =
 +
<b>Внутренним графом</b> (англ. ''Inside graph'') (относительно цикла <tex>C</tex>) будем называть подграф графа <tex>G'</tex>, порождённый всеми вершинами графа <tex>G'</tex>, лежащими внутри цикла <tex>C</tex>.
 +
}}
 +
{{Определение
 +
|definition =
 +
<b>Внутренними компонентами</b> (англ. ''Inside components'') будем называть компоненты связности внутреннего графа.
 +
}}
 +
В силу связности графа <tex>G'</tex> для любой внутренней компоненты должны существовать рёбра в <tex>G'</tex>, соединяющие её с вершинами цикла <tex>C</tex>.
 +
{{Определение
 +
|definition =
 +
<b>Внутренними частями</b> (англ. ''Inside parts'') будем называть внутренние компоненты вместе со всеми рёбрами, соединяющими компоненту с вершинами цикла <tex>C</tex>, и инцидентными им вершинами, либо рёбра графа <tex>G'</tex>, лежащие внутри цикла <tex>C</tex> и соединяющие две вершины из <tex>C</tex>, вместе с инцидентными такому ребру вершинами
 +
}}
 +
Будем говорить, что внешняя (внутренняя) часть ''встречает цикл'' <tex>C</tex> в своих точках прикрепления к циклу <tex>C</tex>.
 +
{{Лемма
 +
|about=1
 +
|statement =
 +
Любая внешняя часть встречает цикл <tex>C</tex> точно в двух точках, одна из которых лежит в <tex>C(a,b)</tex>, а другая {{---}} в <tex>C(b,a)</tex>.
 +
|proof =
 +
Если внешняя часть встречает цикл <tex>C</tex> точно в одной точке <tex>v</tex>, то <tex>v</tex> является точкой сочленения графа <tex>G</tex>, что невозможно.
 +
 
 +
[[Файл:nb.pic.8.png|420px|рис. 8]]
 +
 
 +
Таким образом, внешняя часть встречает цикл <tex>C</tex> не менее чем в двух точках. Если внешняя часть встречает цикл <tex>C</tex> в двух точках из <tex>C[a,b]</tex> (случай <tex>C[b,a]</tex> рассматривается аналогично), то в <tex>G'</tex> имеется цикл, содержащий внутри себя больше граней, чем цикл <tex>C</tex>, и проходящий через <tex>a</tex> и <tex>b</tex>, что невозможно.
 +
 
 +
[[Файл:nb.pic.9.png|420px|рис. 9]]
 +
 
 +
Итого, внешняя часть встречает цикл <tex>C</tex> хотя бы в двух точках, никакие две из которых не лежат в <tex>C[a,b]</tex> и <tex>C[b,a]</tex>. То есть ровно одна лежит в <tex>C(a,b)</tex> и ровно одна {{---}} в <tex>C(b,a)</tex>.
 +
}}
 +
{{Определение
 +
|definition =
 +
Ввиду леммы 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
 +
|statement =
 +
Существует хотя бы одна <tex>(a,b)</tex> {{---}} разделяющая внутренняя часть.
 +
|proof =
 +
Пусть, от противного, таких частей нет. Тогда, выходя из <tex>a</tex> внутри области, ограниченной <tex>C</tex>, и двигаясь вблизи от <tex>C</tex> по направлению обхода <tex>C</tex> и вблизи от встречающихся внутренних частей, можно уложить ребро <tex>e = ab</tex> внутри цикла <tex>C</tex>, т.е. <tex>G</tex> {{---}} планарный граф, что невозможно.
 +
 
 +
[[Файл:nb.pic.10.png|280px|рис. 10]]
 +
 
 +
}}
 +
{{Лемма
 +
|about=3
 +
|statement =
 +
Существует внешняя часть, встречающая <tex>C(a,b)</tex> в точке <tex>c</tex> и <tex>C(b,a)</tex> {{---}} в точке <tex>d</tex>, для которой найдётся внутренняя часть, являющаяся одновременно <tex>(a,b)</tex> {{---}} разделяющей и <tex>(c,d)</tex> {{---}} разделяющей. <br>
 +
 
 +
[[Файл:nb.pic.11.png|240px|рис. 11]]
 +
 
 +
|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]]
 +
 
 +
Поскольку на участках <tex>C(u_{1},u_{2})</tex> и <tex>C(v_{1},v_{2})</tex> нет точек прикрепления внешних частей, используя жорданову кривую <tex>P</tex>, внутреннюю часть <tex>In_{1}</tex> можно перебросить ("вывернуть" наружу от цикла <tex>C</tex>) во внешнюю область цикла <tex>C</tex>, т.е. уложить её снаружи от цикла <tex>C</tex> и сделать её внешней частью.
 +
Аналогично все остальные <tex>(a,b)</tex> {{---}} разделяющие внутренние части можно перебросить во внешнюю область от цикла <tex>C</tex>. После этого точно так же, как в доказательстве леммы 2, ребро <tex>e = ab</tex> можно уложить внутри цикла <tex>C</tex>, так как не останется <tex>(a,b)</tex> {{---}} разделяющих внутренних частей. Следовательно, мы получим укладку графа <tex>G</tex>, что невозможно.
 +
}}
 +
 
 +
 
 +
== Разбор случаев взаимного положения вершин ''a, b, c, d, u1, u2, v1, v2'' ==
 +
* Пусть пара вершин <tex>\ v_1  </tex> и <tex>\ v_2  </tex> <b> является </b> <tex>(a, b)</tex> {{---}} разделяющей. <br>
 +
*: Тогда, в частности, <tex>v_2 \ne a</tex>  и  <tex> v_1 \ne b</tex>.
 +
*: В этом случае граф <tex>G</tex> содержит подграф, гомеоморфный <tex>\ K_{3,3}  </tex> (отметим, что в <tex> In </tex> существует простая <tex>(v_1, v_2)</tex> {{---}} цепь).
 +
 
 +
;:  [[Файл:Case_1.png|270px|рис. 7.1]]
 +
 
 +
*  Пусть пара вершин <tex>v_1</tex> и <tex>v_2</tex> <b> не является </b> <tex>(a, b)</tex> {{---}} разделяющей. <br>
 +
*: Тогда <tex>v_1, v_2</tex> лежат на <tex>C[a, b]</tex> или на <tex>C[b, a]</tex>.
 +
*: Без ограничения общности будет считать, что <tex>v_1</tex> и <tex>v_2</tex> лежат на <tex>C[a, b]</tex>.<br>
 +
*: <br>
 +
*# <b>Пусть <tex>v_1</tex> и <tex>v_2</tex> лежат на <tex>C(a, b)</tex>, т.е. <tex>v_1 \ne b</tex> и <tex>v_2 \ne a</tex>. <br></b>
 +
*## Пусть <tex>u_2</tex> лежит на <tex>C(d, a)</tex>.<br>
 +
*##: Тогда в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex>.
 +
*##: [[Файл:Сase_2.1.1.png|200px|рис. 7.3]]
 +
*## Пусть <tex>u_2 = d</tex>.<br>
 +
*##:Тогда во внешней части <tex>In</tex> имеется вершина <tex>w</tex> и три простые цепи от <tex>w</tex> соответственно до <tex>d, v_1, v_2</tex>, которые в качестве общей точки имеют только точку <tex>w</tex>.
 +
*##:В этом случае в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex>.<br>
 +
*##:[[Файл:Сase_2.1.2.png|200px|рис. 7.4]]
 +
*## Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>.<br>
 +
*##:Тогда в графе <tex>G</tex> есть подграф, гомеоморфный <tex>K_{3,3}</tex>.<br>
 +
*##:[[Файл:Сase_2.1.3.png|200px|рис. 7.5]]
 +
*#:<br>
 +
*#:Теперь рассмотрим случаи (2 и 3), когда хотя бы одна из вершин <tex>v_1</tex> и <tex>v_2</tex> не лежит на <tex>С(a, b)</tex>.
 +
*#:Без ограничения общности будем считать, что это вершина <tex>v_1</tex>, т.е <tex>v_1 = b</tex>(поскольку  <tex>v_1</tex> лежит на <tex>C[a, b]</tex>).<br>
 +
*#:<br>
 +
*# <b> Пусть <tex>v_2 \ne a</tex>.<br> </b>
 +
*##: Пусть <tex>u_2</tex> лежит на <tex>C(d, a)</tex>.<br>
 +
*##: Тогда в графе <tex>G</tex> есть пограф, гомеоморфный <tex>K_{3,3}</tex>.<br>
 +
*##:[[Файл:Сase_2.2.1.png|200px|рис. 7.6]]
 +
*## Пусть <tex>u_2 = d</tex>.<br>
 +
*##:Тогда в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex>.<br>
 +
*##:[[Файл:Сase_2.2.2.png|220px|рис. 7.7]]
 +
*## Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>.<br>
 +
*##:Тогда в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex>. <br>
 +
*##:[[Файл:Сase_2.2.3.png|200px|рис. 7.8]]
 +
*#:<br>
 +
*#:<br>
 +
*# <b> Пусть <tex>v_2 = a</tex>.<br> </b>
 +
*#:[[Файл:Сase_2.3(a).png|200px|рис. 7.9]]
 +
*#:Рассмотрим теперь пару вершин <tex>u_1</tex> и <tex>u_2</tex>.
 +
*#:Будем считать, что <tex>u_1 = c</tex> и <tex>u_2 = d</tex>, поскольку все другие случаи расположения вершин <tex>u_1</tex> и <tex>u_2</tex> так же, как были рассмотрены все случаи расположения <tex>v_1</tex> и <tex>v_2</tex>.
 +
*#:Пусть <tex>P_1</tex> и <tex>P_2</tex> {{---}} соответственно кратчайшие простые <tex>(a, b)</tex> {{---}} цепь и <tex>(c, d)</tex>-цепь по внутренней части <tex>In</tex>.
 +
*#:[[Файл:Сase_2.3(b).png|200px|рис. 7.10]]
 +
*#:Заметим, что <tex>P_1</tex> и <tex>P_2</tex> имеют общую точку.<br>
 +
*#: <br>
 +
*## Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют более одной общей точки.<br>
 +
*##: Тогда в графе <tex>G</tex> есть подграф, гомеоморфный <tex>K_{3,3}</tex>.<br>
 +
*##: [[Файл:Сase_2.3.1.png|200px|рис. 7.11]]
 +
*## Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют точно одну общую точку <tex>w</tex>.<br>
 +
*##: Тогда в графе <tex>G</tex> есть подграф, гомеоморфный <tex>K_5</tex>.<br>
 +
*##: [[Файл:Сase_2.3.2.png|200px|рис. 7.12]]
 +
 
 +
Таким образом, доказано, что в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex> или <tex>K_5</tex>, что противоречит нашему первому предположению.<br>
 +
}}
 +
 
 +
== См. также ==
 +
* [[Двойственный граф планарного графа]]
 +
* [[Теорема Фари]]
 +
 
 +
== Примечания ==
 +
<references />
 +
 
 +
==Источники информации==
 +
*  [https://ru.wikipedia.org/wiki/Планарный_граф Википедия {{---}} Планарный граф]
 +
*  [http://en.wikipedia.org/wiki/Kuratowski's_theorem Wikipedia {{---}} Kuratowski's theorem]
 +
*  [http://acm.math.spbu.ru/~sk1/download/books/TheoremKuratowski.pdf "Вокруг критерия Куратовского планарности графов" (стр. 118)]
 +
*  Асанов М., Баранский В., Расин В. {{---}}  Дискретная математика {{---}}  Графы, матроиды, алгоритмы
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Укладки графов ]]

Текущая версия на 19:38, 4 сентября 2022

Теорему доказал в 1927 году известный советский математик Лев Семенович Понтрягин, но не опубликовал. Независимо от Понтрягина в 1930 году доказательста нашел и впервые напечатал польский математик Казимир Куратовский. Первые доказательства теоремы Понтрягина-Куратовского были очень сложными. Сравнительно простое доказательство нашел в 1997 г. петербургский школьник Юрий Макарычев.

Теорема:
Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных [math] K_{5} [/math] или [math] K_{3, 3} [/math] .
Доказательство:
[math]\triangleright[/math]

Заметим, что из планарности графа следует планарность гомеоморфного графа и наоборот. В самом деле, пусть [math] G_1 [/math] — плоский граф. Если добавить на нужных ребрах вершины степени [math] 2 [/math] и удалить некотрые вершины степени [math] 2 [/math] в [math] G_1 [/math], получим укладку гомеоморфного графа [math] G_2 [/math]. Таким образом, доказательство необходимости следует из непланарности [math]K_5[/math] и [math]K_{3, 3}[/math].

Докажем достаточность. От противного: пусть существует непланарный граф, который не содержит подграфов, гомеоморфных [math] K_{5} [/math] или [math] K_{3, 3} [/math]. Пусть [math] G [/math] — такой граф с наименьшим возможным числом рёбер, не содержащий изолированных вершин.

G связен

Если [math] G [/math] не связен, то в силу минимальности [math] G [/math] его компоненты связности планарны и, следовательно, сам граф [math] G [/math] планарен.

G — обыкновенный граф

В самом деле, пусть в графе [math] G [/math] есть петля или кратное ребро [math] e [/math]. Тогда в силу минимальности [math] G [/math] граф [math] G - e [/math] планарен. Добавляя ребро [math] e [/math] к графу [math] G - e [/math] получим, что граф [math] G [/math] планарен.

G — блок

Пусть, от противного, в графе есть точка сочленения [math] v [/math]. Через [math] G_1 [/math] обозначим подграф графа [math] G [/math], порождённый вершинами одной из компонент связности графа [math] G - v[/math] и вершинной [math] v [/math], а через [math] G_2 [/math] подграф графа [math] G [/math], порождённый вершинами остальных компонент связности графа [math] G - v [/math] и вершиной [math] v [/math].

В силу минимальности [math] G [/math], [math] G_1 [/math] и [math] G_2 [/math] — планарны.

рис. 1

Возьмём укладку графа [math] G_1 [/math] на плоскости такую, что вершина [math] v [/math] лежит на границе внешней грани. Ее можно получить, взяв любую укладку [math] G_1 [/math] на плоскости, по ней построив укладку на шаре, используя обратную стереографическую проекцию[1], потом повернуть сферу так, чтоб [math] v [/math] оказалась на внешней грани стереографической проекции повернутого шара.

Затем во внешней грани графа [math] G_1 [/math] возьмём укладку графа [math] G_2 [/math] такую, что вершина [math] v [/math] будет представлена на плоскости в двух экземплярах.

рис. 2

Соединим два экземпляра вершины [math] v [/math] пучком жордановых линий, не допуская лишних пересечений с укладками графов [math] G_1 [/math] и [math] G_2 [/math], состоящим из такого количества линий, какова степень вершины [math] v [/math] в графе [math] G_2 [/math]. Далее отбросим вхождение вершины [math] v [/math] в граф [math] G_2 [/math], заменяя инцидентные ей рёбра на жордановы линии, полученные из линий указанного пучка и рёбер.

рис. 3

Таким образом мы получили укладку графа [math] G [/math] на плоскости, что невозможно.

В G нет мостов

Граф [math] G [/math] не равен [math] K_2 [/math] и в нем нет точек сочленения, следовательно в [math] G [/math] нет мостов.

В G' существует цикл, содержащий вершины a и b

Пусть [math] e = ab [/math] — произвольное ребро графа [math] G [/math], [math] G' = G - e [/math].

  1. граф [math] G' [/math] планарен в силу минимальности графа [math] G [/math].
  2. граф [math] G' [/math] связен в силу отсутствия в графе [math] G [/math] мостов.

Пусть [math] a [/math] и [math] b [/math] лежат в одном блоке [math] B [/math] графа [math] G' [/math].

  1. Если [math]|VB| \geqslant 3[/math], то существует цикл графа G', содержащий вершины [math] a [/math] и [math] b [/math].
  2. Если [math] |VB| = 2 [/math], то в [math] B [/math] имеется ребро [math] e' = ab [/math], но тогда в [math] G [/math] имеются кратные рёбра [math] e [/math] и [math] e' [/math], что невозможно.
  3. Если вершины [math] a [/math] и [math] b [/math] лежат в разных блоках графа [math] G' [/math], что существует точка сочленения [math] v [/math], принадлежащая любой простой [math] (a, b) [/math] — цепи графа [math] G' [/math]. Через [math] G'_1 [/math] обозначим подграф графа [math] G' [/math], порождённый вершиной [math] v [/math] и вершинами компоненты связности графа [math] G' - v [/math], содержащей [math] a [/math], а через [math] G'_2 [/math] — подграф графа [math] G' [/math], порождённый вершиной [math] v [/math] и вершинами остальных компонент связности графа [math] G' - v [/math] (в этом множестве лежит вершина [math] b [/math]). Пусть [math] G''_1 = G'_1 + e_1 [/math], где [math] e_1 = vb [/math] — новое ребро.

рис. 4

Заметим, что в графе [math] G''_1 [/math] рёбер меньше, чем в графе [math] G [/math]. Действительно, вместо ребра [math] e [/math] в [math] G''_1 [/math] есть ребро [math] e_1 [/math] и часть рёбер из графа [math] G [/math] осталась в графе [math] G''_2 [/math]. Аналогично, в графе [math] G''_2 [/math] рёбер меньше, чем в графе [math] G [/math].
Теперь в силу минимальности графа [math] G [/math] графы [math] G''_1 [/math] и [math] G''_2 [/math] планарны. Возьмем укладку графа [math] G''_1 [/math] на плоскости такую, что ребро [math] e_1 = av [/math] лежит на границе внешней грани(ее существование доказывается аналогично существованию такой укладки для вершины графа). Во внешней грани графа [math] G''_1 [/math] возьмем укладку графа [math] G''_2 [/math] такую, что ребро [math] e_2 = vb [/math] лежит па границе внешней грани.

рис. 5

Отметим, что опять вершина [math] v [/math] представлена на плоскости в двух экземплярах. Очевидно, добавление ребра [math] e = ab [/math] не меняет планарности графа [math] G''_1 U G''_2[/math]. Склеим оба вхождения вершины [math] v [/math] точно так же, как это мы сделали в предыдущем пункте доказательства.

рис. 6

Сотрем затем ранее добавленные ребра [math] e_1 [/math] и [math] e_2 [/math]. В результате мы получим укладку графа [math] G [/math] на плоскости, что невозможно. Утверждение доказано.

Вспомогательные определения и утверждение об одновременно разделяющейся внутренней части

Среди всех укладок графа [math]G'[/math] на плоскости и среди всех циклов [math]C[/math], содержащих [math]a[/math] и [math]b[/math], зафиксируем такую укладку и такой цикл, что внутри области, ограниченной циклом [math]C[/math], лежит максимальное возможное число граней графа [math]G'[/math]. Зафиксируем один из обходов по циклу [math]C[/math] (на рисунках будем рассматривать обход по часовой стрелке по циклу [math]C[/math]). Для вершин [math]u[/math] и [math]v[/math] цикла [math]C[/math] через [math]C[u,v][/math] будем обозначать простую [math](u,v)[/math] — цепь, идущую по циклу [math]C[/math] от [math]u[/math] до [math]v[/math] в направлении обхода цикла. Конечно, [math]C[u,v] \ne C[v,u][/math]. Положим [math]C(u,v) = C[u,v] \setminus[/math] {[math]u,v[/math]}, т.е. [math]C(u,v)[/math] получено из [math]C[u,v][/math] отбрасыванием вершин [math]u[/math] и [math]v[/math].

Определение:
Внешним графом (англ. Outside graph) (относительно цикла [math]C[/math]) будем называть подграф графа [math]G'[/math], порождённый всеми вершинами графа [math]G'[/math], лежащими снаружи от цикла [math]C[/math].


Определение:
Внешними компонентами (англ. Outside components) будем называть компоненты связности внешнего графа.

В силу связности графа [math]G'[/math] для любой внешней компоненты должны существовать рёбра в [math]G'[/math], соединяющие её с вершинами цикла [math]C[/math].

Определение:
Внешними частями (англ. Outside parts) будем называть внешние компоненты вместе со всеми рёбрами, соединяющими компоненту с вершинами цикла [math]C[/math], и инцидентными им вершинами , либо рёбра графа [math]G'[/math], лежащие снаружи от цикла [math]C[/math] и соединяющие две вершины из [math]C[/math], вместе с инцидентными такому ребру вершинами.

рис. 7

Определение:
Внутренним графом (англ. Inside graph) (относительно цикла [math]C[/math]) будем называть подграф графа [math]G'[/math], порождённый всеми вершинами графа [math]G'[/math], лежащими внутри цикла [math]C[/math].


Определение:
Внутренними компонентами (англ. Inside components) будем называть компоненты связности внутреннего графа.

В силу связности графа [math]G'[/math] для любой внутренней компоненты должны существовать рёбра в [math]G'[/math], соединяющие её с вершинами цикла [math]C[/math].

Определение:
Внутренними частями (англ. Inside parts) будем называть внутренние компоненты вместе со всеми рёбрами, соединяющими компоненту с вершинами цикла [math]C[/math], и инцидентными им вершинами, либо рёбра графа [math]G'[/math], лежащие внутри цикла [math]C[/math] и соединяющие две вершины из [math]C[/math], вместе с инцидентными такому ребру вершинами

Будем говорить, что внешняя (внутренняя) часть встречает цикл [math]C[/math] в своих точках прикрепления к циклу [math]C[/math].

Лемма (1):
Любая внешняя часть встречает цикл [math]C[/math] точно в двух точках, одна из которых лежит в [math]C(a,b)[/math], а другая — в [math]C(b,a)[/math].
Доказательство:
[math]\triangleright[/math]

Если внешняя часть встречает цикл [math]C[/math] точно в одной точке [math]v[/math], то [math]v[/math] является точкой сочленения графа [math]G[/math], что невозможно.

рис. 8

Таким образом, внешняя часть встречает цикл [math]C[/math] не менее чем в двух точках. Если внешняя часть встречает цикл [math]C[/math] в двух точках из [math]C[a,b][/math] (случай [math]C[b,a][/math] рассматривается аналогично), то в [math]G'[/math] имеется цикл, содержащий внутри себя больше граней, чем цикл [math]C[/math], и проходящий через [math]a[/math] и [math]b[/math], что невозможно.

рис. 9

Итого, внешняя часть встречает цикл [math]C[/math] хотя бы в двух точках, никакие две из которых не лежат в [math]C[a,b][/math] и [math]C[b,a][/math]. То есть ровно одна лежит в [math]C(a,b)[/math] и ровно одна — в [math]C(b,a)[/math].
[math]\triangleleft[/math]
Определение:
Ввиду леммы 1 будем говорить, что любая внешняя часть является [math](a,b)[/math] — разделяющей частью (англ. separating part), поскольку она встречает и [math]C(a,b)[/math], и [math]C(b,a)[/math].

Аналогично можно ввести понятие [math](a,b)[/math] — разделяющей внутренней части. Заметим, что внутренняя часть может встречать цикл [math]C[/math], вообще говоря, более чем в двух точках, но не менее чем в двух точках.

Лемма (2):
Существует хотя бы одна [math](a,b)[/math] — разделяющая внутренняя часть.
Доказательство:
[math]\triangleright[/math]

Пусть, от противного, таких частей нет. Тогда, выходя из [math]a[/math] внутри области, ограниченной [math]C[/math], и двигаясь вблизи от [math]C[/math] по направлению обхода [math]C[/math] и вблизи от встречающихся внутренних частей, можно уложить ребро [math]e = ab[/math] внутри цикла [math]C[/math], т.е. [math]G[/math] — планарный граф, что невозможно.

рис. 10
[math]\triangleleft[/math]
Лемма (3):
Существует внешняя часть, встречающая [math]C(a,b)[/math] в точке [math]c[/math] и [math]C(b,a)[/math] — в точке [math]d[/math], для которой найдётся внутренняя часть, являющаяся одновременно [math](a,b)[/math] — разделяющей и [math](c,d)[/math] — разделяющей.
рис. 11
Доказательство:
[math]\triangleright[/math]

Пусть, от противного, лемма 3 неверна. Упорядочим [math](a,b)[/math] — разделяющие внутренние части в порядке их прикрепления к циклу [math]C[/math] при движении по циклу от [math]a[/math] до [math]b[/math] и обозначим их соответственно через [math]In_{1},In_{2},\dots[/math] Пусть [math]u_{1}[/math] и [math]u_{2}[/math] — первая и последняя вершины из [math]C(a,b)[/math], в которых [math]In_{1}[/math] встречает цикл [math]C[/math], а [math]v_{1}[/math] и [math]v_{2}[/math] — первая и последняя вершины из [math]C(b,a)[/math], в которых [math]In_{1}[/math] встречает цикл [math]C[/math] (возможно, вообще говоря, [math]u_{1} = u_{2}[/math] или [math]v_{1} = v_{2}[/math]). Поскольку лемма 3 неверна, для любой внешней части обе её вершины, в которых она встречает [math]C[/math], лежат либо на [math]C[v_{2},u_{1}][/math], либо на [math]C[u_{2},v_{1}][/math]. Тогда снаружи цикла [math]C[/math] можно провести жорданову кривую [math]P[/math], не пересекая рёбер графа [math]G'[/math], соединяющую [math]v_{2}[/math] с [math]u_{1}[/math].

рис. 12

Поскольку на участках [math]C(u_{1},u_{2})[/math] и [math]C(v_{1},v_{2})[/math] нет точек прикрепления внешних частей, используя жорданову кривую [math]P[/math], внутреннюю часть [math]In_{1}[/math] можно перебросить ("вывернуть" наружу от цикла [math]C[/math]) во внешнюю область цикла [math]C[/math], т.е. уложить её снаружи от цикла [math]C[/math] и сделать её внешней частью.

Аналогично все остальные [math](a,b)[/math] — разделяющие внутренние части можно перебросить во внешнюю область от цикла [math]C[/math]. После этого точно так же, как в доказательстве леммы 2, ребро [math]e = ab[/math] можно уложить внутри цикла [math]C[/math], так как не останется [math](a,b)[/math] — разделяющих внутренних частей. Следовательно, мы получим укладку графа [math]G[/math], что невозможно.
[math]\triangleleft[/math]


Разбор случаев взаимного положения вершин a, b, c, d, u1, u2, v1, v2

  • Пусть пара вершин [math]\ v_1 [/math] и [math]\ v_2 [/math] является [math](a, b)[/math] — разделяющей.
    Тогда, в частности, [math]v_2 \ne a[/math] и [math] v_1 \ne b[/math].
    В этом случае граф [math]G[/math] содержит подграф, гомеоморфный [math]\ K_{3,3} [/math] (отметим, что в [math] In [/math] существует простая [math](v_1, v_2)[/math] — цепь).
рис. 7.1
  • Пусть пара вершин [math]v_1[/math] и [math]v_2[/math] не является [math](a, b)[/math] — разделяющей.
    Тогда [math]v_1, v_2[/math] лежат на [math]C[a, b][/math] или на [math]C[b, a][/math].
    Без ограничения общности будет считать, что [math]v_1[/math] и [math]v_2[/math] лежат на [math]C[a, b][/math].

    1. Пусть [math]v_1[/math] и [math]v_2[/math] лежат на [math]C(a, b)[/math], т.е. [math]v_1 \ne b[/math] и [math]v_2 \ne a[/math].
      1. Пусть [math]u_2[/math] лежит на [math]C(d, a)[/math].
        Тогда в графе [math]G[/math] имеется подграф, гомеоморфный [math]K_{3,3}[/math].
        рис. 7.3
      2. Пусть [math]u_2 = d[/math].
        Тогда во внешней части [math]In[/math] имеется вершина [math]w[/math] и три простые цепи от [math]w[/math] соответственно до [math]d, v_1, v_2[/math], которые в качестве общей точки имеют только точку [math]w[/math].
        В этом случае в графе [math]G[/math] имеется подграф, гомеоморфный [math]K_{3,3}[/math].
        рис. 7.4
      3. Пусть [math]u_2[/math] лежит на [math]C(b, d)[/math].
        Тогда в графе [math]G[/math] есть подграф, гомеоморфный [math]K_{3,3}[/math].
        рис. 7.5

      Теперь рассмотрим случаи (2 и 3), когда хотя бы одна из вершин [math]v_1[/math] и [math]v_2[/math] не лежит на [math]С(a, b)[/math].
      Без ограничения общности будем считать, что это вершина [math]v_1[/math], т.е [math]v_1 = b[/math](поскольку [math]v_1[/math] лежит на [math]C[a, b][/math]).

    2. Пусть [math]v_2 \ne a[/math].
      1. Пусть [math]u_2[/math] лежит на [math]C(d, a)[/math].
        Тогда в графе [math]G[/math] есть пограф, гомеоморфный [math]K_{3,3}[/math].
        рис. 7.6
      2. Пусть [math]u_2 = d[/math].
        Тогда в графе [math]G[/math] имеется подграф, гомеоморфный [math]K_{3,3}[/math].
        рис. 7.7
      3. Пусть [math]u_2[/math] лежит на [math]C(b, d)[/math].
        Тогда в графе [math]G[/math] имеется подграф, гомеоморфный [math]K_{3,3}[/math].
        рис. 7.8


    3. Пусть [math]v_2 = a[/math].
      рис. 7.9
      Рассмотрим теперь пару вершин [math]u_1[/math] и [math]u_2[/math].
      Будем считать, что [math]u_1 = c[/math] и [math]u_2 = d[/math], поскольку все другие случаи расположения вершин [math]u_1[/math] и [math]u_2[/math] так же, как были рассмотрены все случаи расположения [math]v_1[/math] и [math]v_2[/math].
      Пусть [math]P_1[/math] и [math]P_2[/math] — соответственно кратчайшие простые [math](a, b)[/math] — цепь и [math](c, d)[/math]-цепь по внутренней части [math]In[/math].
      рис. 7.10
      Заметим, что [math]P_1[/math] и [math]P_2[/math] имеют общую точку.

      1. Пусть цепи [math]P_1[/math] и [math]P_2[/math] имеют более одной общей точки.
        Тогда в графе [math]G[/math] есть подграф, гомеоморфный [math]K_{3,3}[/math].
        рис. 7.11
      2. Пусть цепи [math]P_1[/math] и [math]P_2[/math] имеют точно одну общую точку [math]w[/math].
        Тогда в графе [math]G[/math] есть подграф, гомеоморфный [math]K_5[/math].
        рис. 7.12
Таким образом, доказано, что в графе [math]G[/math] имеется подграф, гомеоморфный [math]K_{3,3}[/math] или [math]K_5[/math], что противоречит нашему первому предположению.
[math]\triangleleft[/math]

См. также

Примечания

Источники информации