Изменения
Нет описания правки
[[Файл:p-k.3.png|thumb|right|рис. 3]]
Таким образом мы получили укладку графа <tex> G </tex> на плоскости, что невозможно.
Среди всех укладок графа <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] ≠ C[v,u]</math>. Положим <math>C(u,v) = C[u,v]\{u,v}</math>, т.е. <math>C(u,v)</math> получено из <math>C[u,v]</math> отбрасыванием вершин <math>u</math> и <math>v</math>.
{{Определение:
|definition =
Внешним графом (относительно цикла <math>C</math>) будем называть подграф графа <math>G'</math>, порождённый всеми вершинами графа <math>G'</math>, лежащими снаружи от цикла <math>C</math>.
}}
{{Определение:
|definition =
Внешними компонентами будем называть компоненты связности внешнего графа.
}}
В силу связности графа <math>G'</math> для любой внешней компоненты должны существовать рёбра в <math>G'</math>, соединяющие её с вершинами цикла <math>C</math>.
{{Определение:
|definition =
Внешними частями будем называть:
a) внешние компоненты вместе со всеми рёбрами, соединяющими компоненту с вершинами цикла <math>C</math>, и инцидентными им вершинами;
б) рёбра графа <math>G'</math>, лежащие снаружи от цикла <math>C</math> и соединяющие две вершины из <math>C</math>, вместе с инцидентными такому ребру вершинами.
}}
{{Определиние:
|definition =
Внутренним графом (относительно цикла <math>C</math>) будем называть подграф графа <math>G'</math>, порождённый всеми вершинами графа <math>G'</math>, лежащими внутри цикла <math>C</math>.
}}
{{Определение:
|definition =
Внутренними компонентами будем называть компоненты связности внутреннего графа.
}}
В силу связности графа <math>G'</math> для любой внутренней компоненты должны существовать рёбра в <math>G'</math>, соединяющие её с вершинами цикла <math>C</math>.
{{Определение:
|definition =
Внутренними частями будем называть:
a) внутренние компоненты вместе со всеми рёбрами, соединяющими компоненту с вершинами цикла <math>C</math>, и инцидентными им вершинами;
б) рёбра графа <math>G'</math>, лежащие внутри цикла <math>C</math> и соединяющие две вершины из <math>C</math>, вместе с инцидентными такому ребру вершинами.
}}
Будем говорить, что внешняя (внутренняя) часть ''встречает цикл'' <math>C</math> в своих точках прикрепления к циклу <math>C</math>.
{{Утверждение 5:
|statement =
Любая внешняя часть встречает цикл <math>C</math> точно в двух точках, одна из которых лежит в <math>C(a,b)</math>, а другая - в <math>C(b,a)</math>.
|proof =
Если внешняя часть встречает цикл <math>C</math> точно в одной точке <math>v</math>, то <math>v</math> является точкой сочленения графа <math>G</math>, что невозможно.
Таким образом, внешняя часть встречает цикл <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>, что невозможно.
Итого, внешняя часть встречает цикл <math>C</math> хотя бы в двух точках, никакие две из которых не лежат в <math>C[a,b]</math> и <math>C[b,a]</math>. То есть ровно одна лежит в <math>C[a,b]</math> и ровно одна - в <math>C[b,a]</math>.
}}
{{Определение:
|definition =
Ввиду утверждения 5 будем говорить, что любая внешняя часть является <math>(a,b)</math>-разделяющей частью, поскольку она встречает и <math>C(a,b)</math>, и <math>C(b,a)</math>.
}}
Аналогично можно ввести понятие <math>(a,b)</math>-разделяющей внутренней части. Заметим, что внутрення часть может встречать цикл <math>C</math>, вообще говоря, более чем в двух точках, но не менее чем в двух точках.
{{Утверждение 6:
|statement =
Существует хотя бы одна <math>(a,b)</math>-разделяющая внутренняя часть.
|proof =
Пусть, от противного, таких частей нет. Тогда, выходя из <math>a</math> внутри области, ограниченной <math>C</math>, и двигаясь вблизи от <math>C</math> по направлению обхода <math>C</math> и вблизи от встречающиъся внутренних частей, можно уложить ребро <math>e = ab</math> внутри цикла <math>C</math>, т.е. <math>G</math> - планарный граф, что невозможно.
}}
{{Утверждение 7:
|statement =
Существует внешняя часть, встречающая <math>C(a,b)</math> в точке <math>c</math> и <math>C(b,a)</math> - в точке <math>d</math>, для которой найдётся внутренняя часть, являющаяся одновременно <math>(a,b)</math>-разделяющей и <math>(c,d)</math>-разделяющей.
|proof =
Пусть, от противного, утверждение 7 неверно. Упорядочим <math>(a,b)</math>-разделяющие внутренние части в порядке их прикрепления к циклу <math>C</math> при движении по циклу от <math>a</math> до <math>b</math> и обозначим их соответственно через <math>In_{1},In_{2},...</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>). Поскольку 7 неверно, для любой внешней части обе её вершины, в которых она встречает <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>.
Поскольку на участках <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>. После этого точно так же, как в доказательстве утверждения 6, ребро <math>e = ab</math> можно уложить внутри цикла <math>C</math>, так как не останется <math>(a,b)</math>-разделяющих внутренних частей. Следовательно, мы получим укладку графа <math>G</math>, что невозможно.
}}
==== Разбор случаев взаимного положения ''a, b, c, d, u1, u2, v1, v2'' ====
