Изменения

|about=Теорема об укладке графа с планарными компонентами реберной двусвязности.|statement=Если [[Отношение реберной двусвязности|компоненты реберной двусвязности ]] [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа ]] <tex>G</tex> [[Укладка графа на плоскости|планарны]], то и сам граф <tex>G</tex> планарен.

|id=l1|about=I|statement=Граф <tex>G</tex> планарен тогда и только тогда , когда он обладает укладкой на сфере

Рассмотрим укладку графа <tex>G</tex> на сфере. Возьмем на сфере точку <tex>N</tex> , не лежащую на ребре , и не вершину. Выберем на сфере точку <tex>S</tex> противолежащую <tex>N</tex> (<tex>N</tex> и <tex>S</tex> лежат на одном диаметре и при этом не совпадают). Проведем через точку <tex>S</tex> касательную к сфере плоскость. Спроектируем на плоскость все точки сферы, проведя всевозможные все возможные лучи из точки <tex>N</tex> через точки сферы до плоскостипересечения с плоскостью (рис. 1) . Ясно, что эта проекция дает укладку графа <tex>G</tex> на плоскости. [[Файл: Planar_edge_biconnected_1.png|390px|thumb|center|рис. 1. Проекция графа со сферы на плоскость. <tex>S</tex> {{---}} точка касания, <tex>N</tex> {{---}} противоположная точка.]] 

|id=l2|about=II|statement=Для любого выделенного ребра планарного графа найдется такая укладка графа на плоскости, что выделенное ребро будет лежать на границе внешней грани.

Сначала возьмем Возьмем укладку графа на сфере. Перенесем эту укладку графа на сфере в укладку на плоскости так как это сделано в [[#l1|лемме III]], за точку <tex>N</tex> возьмем точку на сфере , не лежащую на ребре, не являющуюся вершиной, и принадлежащую грани на границе которой лежит выделенное ребро. Полученная укладка на плоскости обладает нужным нам свойством(рис. 2). [[Файл: Planar_edge_biconnected_2.png|220px|thumb|center|рис. 2.]]

Докажем утверждение теоремы для одной из компоненты компонент связности графа <tex>G</tex>. Ясно, что имея укладки на плоскости каждой из компонент связности какого-либо графа , мы можем получить укладку на плоскости и всего графа.Итак пусть граф <tex>G</tex> - связен. Рассмотрим связный под-граф подграф <tex>T</tex> графа компонент реберной двусвязности графа <tex>G</tex>. Согласно Из [[Граф компонент реберной двусвязности|леммелеммы]] и из связности <tex>T</tex> - получаем, что <tex>T</tex> &mdash; [[Дерево, эквивалентные определения|дерево]].  Докажем индукцией по числу вершин в графе <tex>T</tex>, что под-граф подграф <tex>G'</tex> графа <tex>G</tex> состоящий из компонент реберной двусвязности и [[Мост,_эквивалентные_определения|мостов ]] графа <tex>G</tex> принадлежащих графа графу <tex>T</tex> планарен (далее будем говритьговорить, что <tex>G'</tex> соответствует <tex>T</tex>).

<div style="border:1px dashed #000; width:90%; margin: 10px; padding:4px; background-color: #fdfdfd; padding-left:10px;">Если <tex>|VT| = 1</tex>, то граф <tex>T</tex> {{--- }} тривиальныйграф. Его единственная вершина - это компонента реберной двусвязности графа <tex>G</tex>, которая по утверждению условию теоремы - планарна.</div>

<div style="border:1px dashed #000; width:90%; margin: 10px; padding:4px; background-color: #fdfdfd; padding-left:10px;">Пусть утверждение верно для <tex>|VT| < m</tex>. Рассмотрим дерево <tex>T</tex>, для которого <tex>|VT| = m > 1</tex>, и соответствующий <tex>T</tex> под-граф подграф <tex>G'</tex> графа <tex>G</tex>. Докажем, что <tex>G'</tex> планарен.  Положим <tex>G_1</tex> - блок &mdash; компонента реберной двусвязности графа <tex>G'</tex> являющийся висячей вершиной дерева <tex>T</tex>, a <tex>e</tex> - &mdash; [[Мост,_эквивалентные_определения|мост ]] в <tex>G'</tex> инцидентный <tex>G_1</tex> в <tex>T</tex>(рис. 3). <tex>G_1</tex> планарен по утверждению условию теоремы, т.к. блоки компоненты реберной двусвязности графа <tex>G'</tex> совпадают с блоками компонентами реберной двусвязности графа <tex>G</tex>. Далее рассмотрим под-граф подграф <tex>G_2</tex> графа <tex>G'</tex> , соответствующий дереву <tex>T\backslash \{G_1\}</tex>. Он Поскольку <tex>G_1</tex> &mdash; висячая вершина <tex>T</tex>, то <tex>T\backslash \{G_1\}</tex> связен, и, очевидно, также как и <tex>T</tex> является подграфом графа компонент реберной двусвязности <tex>G</tex>. Итак <tex>G_2</tex> планарен по предположению индукции, т.к. <tex>|V(T\backslash \{uG_1\})| = |VT| - 1 = m - 1 < m</tex>. Из определения ребер графа компонент реберной двусвязности получаем, что графы <tex>G_1</tex> и <tex>G_2</tex> соединены в графе <tex>G'</tex> единственным [[Мост,_эквивалентные_определения|мостом]] <tex>e \in G'</tex> инцидентным блоку <tex>G_1</tex> в дереве <tex>T</tex>. Поскольку <tex>T = G_1\cup e\cup G_2</tex>, то и <tex>G' = G_1\cup e\cup G_2</tex>. Покажем как из укладок <tex>G_1</tex> и <tex>G_2</tex> получить укладку <tex>G'</tex>. [[Файл: Planar_edge_biconnected_3.png|240px|thumb|center|рис. 3. Удаление <tex>G_1</tex> из графа компонент реберной двусвязности]] Уложим <tex>G_2</tex> на сфере и уложим <tex>G_1</tex> на плоскости так, чтобы ребро <tex>e_1 \in G_1</tex> смежное с <tex>e</tex> в G' (если таковое имеется) оказалось на границе внешней грани (по [[#l2|лемме II]] это возможно, рис. 4). Если такого ребра <tex>e_1</tex> не существует, значит компонента реберной двусвязности <tex>G_1</tex> &mdash; тривиальный граф, в таком случае возьмем любую укладку <tex>G_1</tex> на плоскости. Пусть <tex>u\in G_2</tex> {{---}} вершина инцидентная <tex>e</tex>. Сожмем часть плоскости, содержащую укладку <tex>G_1</tex>, так, чтобы она вмещалась в одну из граней укладки <tex>G_2</tex> смежную с <tex>u</tex>. Проведем жорднанову кривую, соответствующую ребру <tex>e</tex>, от вершины <tex>u</tex> к инцидентной <tex>e</tex> вершине графа <tex>G_1</tex> так, чтобы она не пересекалась с укладками <tex>G_1</tex> и <tex>G_2</tex>. Мы получили укладку графа <tex>G'</tex> на сфере, а значит (по [[#l1|лемме I]]) <tex>G'</tex> планарен, следовательно предположение индукции верно.

Из определения ребер дерева компонент реберной двусвязности получаем, что графы <tex>G_1</tex> и <tex>G_2</tex> соединены в графе <tex>G'</tex> единственным мостом <tex>e \in G'</tex> инцидентным блоку <tex>G_1</tex> в дереве <tex>T</tex>[[Файл: Planar_edge_biconnected_4.png|thumb|220px|center|рис. Поскольку <tex>T = \{G_1\}\cup e\cup \{G_2\}</tex>, то и <tex>G' = \{G_1\}\cup e\cup \{G_2\}</tex>4. Покажем как из укладок Укладка <tex>G_1</tex> и <tex>G_2</tex> получить укладку <tex>G'на сфере]]</texdiv>.