61
правка
Изменения
м
----
==== Разбор случаев взаимного положения ''a, b, c, d, u1, u2, v1, v2'' ====
Добавлены категории, замена некоторых дефисов длинными тире
__TOC__
{{Теорема
|statement =
Необходимость условия очевидна.
=== Достаточность ===
От противного: пусть существует непланарный граф, который не содержит подграфов, гомеоморфных <tex> K_{5} </tex> или <tex> K_{3, 3} </tex>. Пусть <tex> G </tex> - — такой граф с наименьшим возможным числом рёбер, не содержащий изолированных вершин.
==== G связен ====
Если <tex> G </tex> не связен, то его компоненты связности планарны и, следовательно, сам граф <tex> G </tex> планарен.
==== G - — обыкновенный граф ====
В самом деле, пусть в графе <tex> G </tex> есть петля или кратное ребро <tex> e </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> на плоскости, что невозможно.
<br/> <br/>
Пусть <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>, принадлежащая любой простой (a, b)-цепи графа <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)
[[Файл: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/>
{{Лемма
|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>, что невозможно (см. рис. 9).
{{Лемма
|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>-разделяющей (см. рис. 12).
[[Файл:pict-6.jpg|center|120px|рис. 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> (см. рис. 13).
[[Файл:pict-7.jpg|center|160px|рис. 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> и сделать её внешней частью.
}}
Рассмотрим 2 случая.
[[Файл:Case_1.png|thumb|right|рис. 1]]
2.1.3. Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>.<br>
Тогда в графе <tex>G</tex> есть подграф, гомеоморфный <tex>KK_{3,3}</tex>(рис. 5).<br>
<p>
2.3. Пусть <tex>v_2 = a</tex>(рис. 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>(рис. 10).
Заметим, что <tex>P_1</tex> и <tex>P_2</tex> имеют общую точку.<br>
==Литература==
* Асанов М,., Баранский В., Расин В. - — Дискретная математика - — Графы, матроиды, алгоритмы
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов ]]
