Изменения

Предварительно заметим, что в доказательстве используются утверждения лемм [[Укладка графа с планарными компонентами реберной двусвязности#l1|леммы I]] и [[Укладка графа с планарными компонентами реберной двусвязности#l2|леммы II]] из статьи [[Укладка графа с планарными компонентами реберной двусвязности]]. Итак, уложим <tex>G_2</tex> на сфере и уложим <tex>G_1</tex> на плоскости так, чтобы ребро <tex>e_1 \in G_1</tex> смежное с <tex>v_1</tex> (если таковое имеется) оказалось на границе внешней грани (по [[#l2|лемме II]] это возможно). Если такого ребра <tex>e_1</tex> не существует, значит вершина <tex>v_1</tex> изолирована, в таком случае возьмем любую укладку <tex>G_1</tex> на плоскости и переместим точку, соответствующую <tex>v_1</tex> во внешнюю грань. Сожмем Иначе сожмем часть плоскости, содержащую укладку <tex>G_1</tex> так, чтобы она вмещалась в одну из граней укладки <tex>G_2</tex> смежную с <tex>v_1</tex>. Рассмотрим множество <tex>U</tex> вершин смежных с <tex>v_1</tex>. Уберем кривые, соответствующие ребрам, инцидентным <tex>v_1</tex>. Ясно, что после этого множество вершин <tex>U</tex> лежит на внешней границе укладки <tex>G_1</tex>. Соединим теперь каждую вершину из <tex>U</tex> c <tex>v_2</tex> непересекающимися жордановыми линиями так, чтобы они не задевали укладок <tex>G_1</tex> и <tex>G_2</tex>(рис. 1). Таким образом мы совместили вершины <tex>v_1</tex> и <tex>v_2</tex> в вершине <tex>v_2</tex>, а значит получили укладку графа <tex>G</tex> на сфере, следовательно <tex>G</tex> - планарен.[[Файл: Planar_vertex_biconnected_1.png|300px|center|thumb|рис. 1.]]

Итак пусть граф <tex>G</tex> связен. Если <tex>G = K_1</tex>, то <tex>G</tex> очевидно планерен, поэтому предположим, что <tex>|EG| \ge geqslant 1</tex> , а значит имеется по-крайней мере один блок в <tex>G</tex>. Рассмотрим связный подграф <tex>T</tex> графа блоков и точек сочленений графа <tex>G</tex> такой, что <tex>\forall v</tex> - т.с. <tex>G</tex> имеем <tex>\deg(v) \ge geqslant 2</tex>. Из [[Граф блоков-точек сочленения#lemma1|леммы]] и из связности <tex>T</tex> получаем, что <tex>T</tex> &mdash; двудольное [[Дерево, эквивалентные определения|дерево]].

<div style="border:1px solid dashed #000; width:90%; margin: 10px; padding:4px; background-color: #fdfdfd; padding-left:10px;">

<div style="border:1px solid dashed #000; width:90%; margin: 10px; padding:4px; background-color: #fdfdfd; padding-left:10px;">

Положим <tex>G_1</tex> &mdash; это блок графа <tex>G'</tex> являющийся висячей вершиной дерева <tex>T</tex> (вспомним, что в дереве, в котором более одной вершины, всегда есть есть висячие вершины, и то, что висячими вершинами в графе блоков и т.с. не могут быть т.с.), a <tex>v</tex> {{---}} т.с. в <tex>G'</tex> смежная с <tex>G_1</tex> в <tex>T</tex>. <tex>G_1</tex> планарен по утверждению теоремы, т.к. блоки графа <tex>G'</tex> совпадают с блоками графа <tex>G</tex>. Заметим, что <tex>\deg(v) > 1</tex>, т.к. <tex>v</tex> {{---}} т.с., следовательно не висячая. Рассмотрим два случая:

#<tex>\deg(v) = 2</tex> в <tex>T</tex>(рис. 2). Обозначим за <tex>T'</tex> <tex>T\backslash \{u,v\}</tex>. Поскольку степень ни одной из т.с. <tex>G'</tex> принадлежащих <tex>T</tex> (кроме удаленной <tex>v</tex>) не уменьшилась, значит <tex>T'</tex> удовлетворяет условиям на <tex>T</tex> из предположения индукции. Заметим, что <tex>VT' = VT - 2 = m - 2 < m</tex>. Заметим также, что <tex>T'</tex> связен, т.к. <tex>u</tex> и <tex>v</tex> по очереди были висячими вершинами <tex>T</tex> и <tex>T\backslash \{u\}</tex>.[[Файл: Planar vertex biconnected 2.png|270px|center|thumb|рис. 2. Красные {{---}} точки сочленений. Голубые {{---}} блоки.]]#<tex>\deg (v) > 2</tex> в <tex>T</tex>(рис. 3). Обозначим за <tex>T'</tex> <tex>T\backslash \{u\}</tex>. Поскольку степень ни одной из т.с. <tex>G'</tex> принадлежащих <tex>T</tex> (кроме <tex>v</tex>, для нее степень уменьшилась ровно на <tex>1</tex>) не уменьшилась, а для вершины <tex>v</tex> в <tex>T'</tex> верно, что <tex>\deg(v) >= 2</tex>, то <tex>T'</tex> удовлетворяет условиям на <tex>T</tex> из предположения индукции. Заметим, что <tex>VT' = VT - 1 = m - 1 < m</tex>. Заметим также, что <tex>T'</tex> связен, т.к. <tex>u</tex> была висячей вершиной в <tex>T</tex>.[[Файл: Planar vertex biconnected 3.png|270px|center|thumb|рис. 3. Красные {{---}} точки сочленений. Голубые {{---}} блоки.]]

==ИсточникиСм. также==*[[Укладка_графа_с_планарными_компонентами_реберной_двусвязности|Укладка графа с планарными компонентами реберной двусвязности]]

H* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. Whitney {{— ISBN 5-93972-076-}} 5 * H. Whitney '''Non-separable and planar graphs {{---}} ''' — Trans. Amer. Math. Soc., 1932. [[Категория: Алгоритмы и структуры данных]][[Категория: Укладки графов ]]