Изменения

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

|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> {{---}} противоположная точка.]] 

Сначала возьмем Возьмем укладку графа на сфере. Перенесем эту укладку графа на сфере в укладку на плоскости так как это сделано в [[#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 solid 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 style="border:1px solid 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 \{G_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>.

Положим <tex>G_1</tex> - блок графа <tex>G'</tex> являющийся висячей вершиной дерева <tex>T</tex>, a <tex>e</tex> - мост в <tex>G'</tex> инцидентный <tex>G_1</tex> в <tex>T</tex>[[Файл: Planar_edge_biconnected_3. <tex>G_1</tex> планарен по утверждению теоремы, тpng|240px|thumb|center|рис.к3. блоки графа Удаление <tex>G'</tex> совпадают с блоками графа <tex>G</tex>. Далее рассмотрим под-граф <tex>G_2G_1</tex> из графа <tex>G'</tex> соответствующий дереву <tex>T\backslash \{G_1\}</tex>. Он планарен по предположению индукции, т.к. <tex>|V(T\backslash \{u\})| = |VT| - 1 = m - 1 < m</tex>. компонент реберной двусвязности]]

Из определения ребер дерева компонент реберной двусвязности получаем, что графы Уложим <tex>G_1G_2</tex> на сфере и уложим <tex>G_2G_1</tex> соединены в графе на плоскости так, чтобы ребро <tex>G'e_1 \in G_1</tex> единственным мостом смежное с <tex>e \in </tex> в G'(если таковое имеется) оказалось на границе внешней грани (по [[#l2|лемме II]] это возможно, рис. 4). Если такого ребра <tex>e_1</tex> инцидентным блоку не существует, значит компонента реберной двусвязности <tex>G_1</tex> &mdash; тривиальный граф, в дереве таком случае возьмем любую укладку <tex>TG_1</tex>на плоскости. Поскольку Пусть <tex>T = u\in G_2</tex> {G_1\{---}}\cup вершина инцидентная <tex>e\cup \{G_2\}</tex>. Сожмем часть плоскости, то и содержащую укладку <tex>G' = \{G_1\}\cup e\cup \{</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_2</tex> на сфере и уложим <tex>G_1</tex> на плоскости так, чтобы ребро <tex>e_1 \in G_1</tex> смежное с <tex>e</tex> в G' оказалось на границе внешней грани (по [[#l1Файл: Planar_edge_biconnected_4.png|thumb|220px|лемме II]] это возможно)center|рис. Обозначим за <tex>u</tex> - вершину из <tex>G_2</tex> инцедентную <tex>e</tex>4. Сожмем часть плоскости, содержащую укладку Укладка <tex>G_1</tex> так чтобы она вмещалась в одну из граней укладки и <tex>G_2</tex> смежную с <tex>u</tex>. Проводя ребро <tex>e</tex> от вершины <tex>u</tex> к инцидентоной ему вершине графа <tex>G_1</tex> мы получаем укладку графа <tex>G'</tex> на сфере, а значит (по [[#l1|лемме I]]) <tex>G'</tex> планарен, следовательно предположение индукции верно.

'''Замечание.''' В доказательстве теоремы непосредственно указывается способ получения укладки графа <tex>G</tex> из укладок его компонент реберной двусвязности.==См. также==*[[Укладка_графа_с_планарными_компонентами_вершинной_двусвязности|Укладка графа с планарными компонентами вершинной двусвязности]] ==Источникиинформации== * Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5

Асанов М* H., Баранский ВWhitney '''Non-separable and planar graphs''' — Trans. Amer. Math., Расин ВSoc. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 20011932.