Теорема Понтрягина-Куратовского

Содержание

1 G связен
2 G — обыкновенный граф
3 G — блок
4 В G нет мостов
5 В G' существует цикл, содержащий вершины a и b
6 Вспомогательные определения и утверждение об одновременно разделяющейся внутренней части
7 Разбор случаев взаимного положения вершин a, b, c, d, u1, u2, v1, v2
8 Литература

Теорема:

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных или .

Доказательство:

Заметим, что из планарности графа следует планарность гомеоморфного графа и наоборот. В самом деле, пусть [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]. (рис. 1)

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

рис. 1

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

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

рис. 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)

рис. 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].

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

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

Если [math] |VB| \gt = 3 [/math], то существует цикл графа G', содержащий вершины [math] a [/math] и [math] b [/math].
Если [math] |VB| = 2 [/math], то в [math] B [/math] имеется ребро [math] e' = ab [/math], но тогда в [math] G [/math] имеются кратные рёбра [math] e [/math] и [math] e' [/math], что невозможно.
Если вершины [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)

рис. 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).

рис. 5

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

рис. 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) (относительно цикла ) будем называть подграф графа , порождённый всеми вершинами графа , лежащими снаружи от цикла .

Определение:

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

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

Определение:

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

Определение:

Внутренним графом (англ. Inside graph) (относительно цикла ) будем называть подграф графа , порождённый всеми вершинами графа , лежащими внутри цикла .

Определение:

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

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

Определение:

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

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

Лемма (1):

Любая внешняя часть встречает цикл точно в двух точках, одна из которых лежит в , а другая — в .

Доказательство:

Если внешняя часть встречает цикл [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], что невозможно.

Итого, внешняя часть встречает цикл хотя бы в двух точках, никакие две из которых не лежат в и . То есть ровно одна лежит в и ровно одна — в .

Определение:

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

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

Лемма (2):

Существует хотя бы одна — разделяющая внутренняя часть.

Доказательство:

Пусть, от противного, таких частей нет. Тогда, выходя из внутри области, ограниченной , и двигаясь вблизи от по направлению обхода и вблизи от встречающихся внутренних частей, можно уложить ребро внутри цикла , т.е. — планарный граф, что невозможно.

Лемма (3):

Существует внешняя часть, встречающая в точке и — в точке , для которой найдётся внутренняя часть, являющаяся одновременно — разделяющей и — разделяющей.

Доказательство:

Пусть, от противного, лемма 3 неверна. Упорядочим [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]). Поскольку лемма 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].

Поскольку на участках [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] и сделать её внешней частью.

Аналогично все остальные — разделяющие внутренние части можно перебросить во внешнюю область от цикла . После этого точно так же, как в доказательстве леммы 2, ребро можно уложить внутри цикла , так как не останется — разделяющих внутренних частей. Следовательно, мы получим укладку графа , что невозможно.

Разбор случаев взаимного положения вершин 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] — цепь).

Пусть пара вершин [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].
  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].
  3. Пусть [math]u_2[/math] лежит на [math]C(b, d)[/math].
    
    Тогда в графе [math]G[/math] есть подграф, гомеоморфный [math]K_{3,3}[/math].
  Теперь рассмотрим случаи (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].
  2. Пусть [math]u_2 = d[/math].
    
    Тогда в графе [math]G[/math] имеется подграф, гомеоморфный [math]K_{3,3}[/math].
  3. Пусть [math]u_2[/math] лежит на [math]C(b, d)[/math].
    
    Тогда в графе [math]G[/math] имеется подграф, гомеоморфный [math]K_{3,3}[/math].
3. Пусть [math]v_2 = a[/math].
  
  Рассмотрим теперь пару вершин [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].
  
  Заметим, что [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].
  2. Пусть цепи [math]P_1[/math] и [math]P_2[/math] имеют точно одну общую точку [math]w[/math].
    
    Тогда в графе [math]G[/math] есть подграф, гомеоморфный [math]K_5[/math].