Изменения
Определения выделены жирным, заменены дефисы на тире
Граф [[Укладка_графа_на_плоскости| планарен]] тогда и только тогда, когда он не содержит подграфов, [[Укладка графа на плоскости #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> — {{---}} такой граф с наименьшим возможным числом рёбер, не содержащий изолированных вершин.
=== G связен ===
Если <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>. (рис. 1)
В силу минимальности <tex> G </tex>, <tex> G_1 </tex> и <tex> G_2 </tex> {{- --}} планарны.
[[Файл:New.p-k.1.png|thumb|right|рис. 1]]
Возьмём укладку графа <tex> G_1 </tex> на плоскости такую, что вершина <tex> v </tex> лежит на границе внешней грани. Ее можно получить, взяв любую укладку <tex> G_1 </tex> на плоскости, по ней построив укладку на шаре, используя обратную [http://en.wikipedia.org/wiki/Stereographic_projection стереографическую проекцию], потом повернуть сферу так, чтоб <tex> v </tex> оказалась на внешней грани стереографической проекции повернутого шара.
Граф <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> мостов.
# Если <tex> |VB| >= 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> — {{---}} новое ребро (рис. 4)
[[Файл:New.p-k.4.png|thumb|right|рис. 4]]
Заметим, что в графе <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/>
===Вспомогательные определения и утверждение об одновременно разделяющейся внутренней части===
Среди всех укладок графа <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> (относительно цикла <tex>C</tex>) будем называть подграф графа <tex>G'</tex>, порождённый всеми вершинами графа <tex>G'</tex>, лежащими снаружи от цикла <tex>C</tex>.
}}
{{Определение
|definition =
<b>Внешними компонентами </b> будем называть компоненты связности внешнего графа.
}}
В силу связности графа <tex>G'</tex> для любой внешней компоненты должны существовать рёбра в <tex>G'</tex>, соединяющие её с вершинами цикла <tex>C</tex>.
{{Определение
|definition =
<b>Внешними частями </b> будем называть внешние компоненты вместе со всеми рёбрами, соединяющими компоненту с вершинами цикла <tex>C</tex>, и инцидентными им вершинами , либо рёбра графа <tex>G'</tex>, лежащие снаружи от цикла <tex>C</tex> и соединяющие две вершины из <tex>C</tex>, вместе с инцидентными такому ребру вершинами.
}}
[[Файл:pict-1.jpg|center|200px|рис. 7]][[Файл:pict-2.jpg|center|125px|рис. 8]]
{{Определение
|definition =
<b>Внутренним графом </b> (относительно цикла <tex>C</tex>) будем называть подграф графа <tex>G'</tex>, порождённый всеми вершинами графа <tex>G'</tex>, лежащими внутри цикла <tex>C</tex>.
}}
{{Определение
|definition =
<b>Внутренними компонентами </b> будем называть компоненты связности внутреннего графа.
}}
В силу связности графа <tex>G'</tex> для любой внутренней компоненты должны существовать рёбра в <tex>G'</tex>, соединяющие её с вершинами цикла <tex>C</tex>.
{{Определение
|definition =
<b>Внутренними частями </b> будем называть внутренние компоненты вместе со всеми рёбрами, соединяющими компоненту с вершинами цикла <tex>C</tex>, и инцидентными им вершинами, либо рёбра графа <tex>G'</tex>, лежащие внутри цикла <tex>C</tex> и соединяющие две вершины из <tex>C</tex>, вместе с инцидентными такому ребру вершинами
}}
Будем говорить, что внешняя (внутренняя) часть ''встречает цикл'' <tex>C</tex> в своих точках прикрепления к циклу <tex>C</tex>.
{{Лемма
|statement =
1) Любая внешняя часть встречает цикл <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>, что невозможно.
Таким образом, внешняя часть встречает цикл <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>, что невозможно.
[[Файл:pict-4.jpg|center|рис. 10]]
Итого, внешняя часть встречает цикл <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>, поскольку она встречает и <tex>C(a,b)</tex>, и <tex>C(b,a)</tex>.
}}
Аналогично можно ввести понятие <tex>(a,b)</tex>{{---}} разделяющей внутренней части. Заметим, что внутрення часть может встречать цикл <tex>C</tex>, вообще говоря, более чем в двух точках, но не менее чем в двух точках.
{{Лемма
|statement =
2) Существует хотя бы одна <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> {{- --}} планарный граф, что невозможно.[[Файл:pict-5.jpg|center|180px|рис. 11]]
}}
{{Лемма
|statement =
3) Существует внешняя часть, встречающая <tex>C(a,b)</tex> в точке <tex>c</tex> и <tex>C(b,a)</tex> — {{---}} в точке <tex>d</tex>, для которой найдётся внутренняя часть, являющаяся одновременно <tex>(a,b)</tex>{{---}} разделяющей и <tex>(c,d)</tex>{{---}} разделяющей.
[[Файл:pict-6.jpg|center|160px|рис. 12]]
|proof =
Пусть, от противного, лемма 3 неверна. Упорядочим <tex>(a,b)</tex>{{---}} разделяющие внутренние части в порядке их прикрепления к циклу <tex>C</tex> при движении по циклу от <tex>a</tex> до <tex>b</tex> и обозначим их соответственно через <tex>In_{1},In_{2},...</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>.
[[Файл:pict-7.jpg|center|200px|рис. 13]]
Поскольку на участках <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>, что невозможно.
}}
[[Файл:Case_1.png|thumb|right|рис. 7.1]]
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>. В этом случае граф <tex>G</tex> содержит подграф, гомеоморфный <tex>\ K_{3,3} </tex> (отметим, что в <tex> In </tex> существует простая <tex>(v_1, v_2)</tex>{{---}} цепь) (рис. 7.1).
2. Пусть пара вершин <tex>v_1</tex> и <tex>v_2</tex> не является <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>
2.3. Пусть <tex>v_2 = a</tex> (рис. 7.9).<br>
Рассмотрим теперь пару вершин <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> (рис. 7.10).
Заметим, что <tex>P_1</tex> и <tex>P_2</tex> имеют общую точку.<br>
