Изменения
Новая страница: «{{Теорема |about= Теорема об укладке графа с планарными компонентами реберной двусвязности. |s…»
{{Теорема
|about=
Теорема об укладке графа с планарными компонентами реберной двусвязности.
|statement=
Если компоненты реберной двусвязности графа <tex>G</tex> планарны, то и сам граф <tex>G</tex> планарен.
|proof=
Докажем для начала ряд вспомогательных лемм.
{{Лемма
|about=
I
|statement=
Граф <tex>G</tex> планарен тогда и только тогда когда он обладает укладкой на сфере
|proof=
Рассмотрим укладку графа <tex>G</tex> на сфере. Возьмем на сфере точку <tex>N</tex> не лежащую на ребре и не вершину. Выберем на сфере точку <tex>S</tex> противолежащую <tex>N</tex> (<tex>N</tex> и <tex>S</tex> лежат на одном диаметре и не совпадают). Проведем через точку <tex>S</tex> касательную к сфере плоскость. Спроектируем на плоскость все точки сферы, проведя всевозможные лучи из точки <tex>N</tex> через точки сферы до плоскости. Ясно, что эта проекция дает укладку графа <tex>G</tex> на плоскости.
Обратно рассмотрим укладку графа <tex>G</tex> на плоскости. Возьмем сферу, которая касается плоскости, и обозначим точку касания за <tex>S</tex>. Противолежащую <tex>S</tex> точку на сфере обозначим за <tex>N</tex>. Проведем все возможные лучи от точек плоскости через точки сферы до точки <tex>N</tex>. Ясно что при этом укладка графа <tex>G</tex> на плоскости будет перенесена на некоторую укладку графа <tex>G</tex> на сфере.
}}
{{Лемма
|about=
II
|statement=
Для любого выделенного ребра планарного графа найдется такая укладка графа на плоскости, что выделенное ребро будет лежать на границе внешней грани.
|proof=
Сначала возьмем укладку графа на сфере. Перенесем эту укладку графа на сфере в укладку на плоскости так как это сделано в лемме II, за точку <tex>N</tex> возьмем точку на сфере не лежащую на ребре, не являющуюся вершиной, и принадлежащую грани на границе которой лежит выделенное ребро. Полученная укладка на плоскости обладает нужным нам свойством.
}}
Докажем утверждение теоремы для одной из компоненты связности графа <tex>G</tex>. Ясно, что имея укладки на плоскости каждой из компонент связности какого-либо графа , мы можем получить укладку на плоскости и всего графа.
Итак пусть граф <tex>G</tex> - связен. Рассмотрим связный под-граф <tex>T</tex> графа компонент реберной двусвязности графа <tex>G</tex>. Согласно [[Граф компонент реберной двусвязности|лемме]] из связности <tex>T</tex> - получаем, что <tex>T</tex> [[Дерево, эквивалентные определения|дерево]]. Докажем индукцией по числу вершин в графе <tex>T</tex>, что под-граф <tex>G'</tex> графа <tex>G</tex> состоящий из компонент реберной двусвязности и мостов графа <tex>G</tex> принадлежащих графа <tex>T</tex> планарен (далее будем говрить, что <tex>G'</tex> соответствует <tex>T</tex>).
'''База индукции.'''
Если <tex>|VT| = 1</tex>, то граф <tex>T</tex> - тривиальный. Его единственная вершина - это компонента реберной двусвязности графа <tex>G</tex>, которая по утверждению теоремы - планарна.
'''Индукционный переход.'''
Пусть утверждение верно для <tex>|VT| < m</tex>. Рассмотрим дерево <tex>T</tex>, для которого <tex>|VT| = m > 1</tex>, и соответствующий <tex>T</tex> под-граф <tex>G'</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>. <tex>G_1</tex> планарен по утверждению теоремы, т.к. блоки графа <tex>G'</tex> совпадают с блоками графа <tex>G</tex>. Далее рассмотрим под-граф <tex>G_2</tex> графа <tex>G'</tex> соответствующий дереву <tex>T\backslash \{G_1\}</tex>. Он планарен по предположению индукции, т.к. <tex>|V(T\backslash \{u\})| = |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_2</tex> на сфере и уложим <tex>G_1</tex> на плоскости так, чтобы ребро <tex>e_1 \in G_1</tex> смежное с <tex>e</tex> в G' оказалось на границе внешней грани (по лемме II это возможно). Обозначим за <tex>u</tex> - вершину из <tex>G_2</tex> инцедентную <tex>e</tex>. Сожмем часть плоскости, содержащую укладку <tex>G_1</tex> так чтобы она вмещалась в одну из граней укладки <tex>G_2</tex> смежную с <tex>u</tex>. Проводя ребро <tex>e</tex> от вершины <tex>u</tex> к инцидентоной ему вершине графа <tex>G_1</tex> мы получаем укладку графа <tex>G'</tex> на сфере, а значит (по лемме I) <tex>G'</tex> планарен, следовательно предположение индукции верно.
Рассматривая в качестве <tex>T</tex> граф компонент реберной двусвязности <tex>G</tex> получаем что <tex>G</tex> - планарен.
}}
|about=
Теорема об укладке графа с планарными компонентами реберной двусвязности.
|statement=
Если компоненты реберной двусвязности графа <tex>G</tex> планарны, то и сам граф <tex>G</tex> планарен.
|proof=
Докажем для начала ряд вспомогательных лемм.
{{Лемма
|about=
I
|statement=
Граф <tex>G</tex> планарен тогда и только тогда когда он обладает укладкой на сфере
|proof=
Рассмотрим укладку графа <tex>G</tex> на сфере. Возьмем на сфере точку <tex>N</tex> не лежащую на ребре и не вершину. Выберем на сфере точку <tex>S</tex> противолежащую <tex>N</tex> (<tex>N</tex> и <tex>S</tex> лежат на одном диаметре и не совпадают). Проведем через точку <tex>S</tex> касательную к сфере плоскость. Спроектируем на плоскость все точки сферы, проведя всевозможные лучи из точки <tex>N</tex> через точки сферы до плоскости. Ясно, что эта проекция дает укладку графа <tex>G</tex> на плоскости.
Обратно рассмотрим укладку графа <tex>G</tex> на плоскости. Возьмем сферу, которая касается плоскости, и обозначим точку касания за <tex>S</tex>. Противолежащую <tex>S</tex> точку на сфере обозначим за <tex>N</tex>. Проведем все возможные лучи от точек плоскости через точки сферы до точки <tex>N</tex>. Ясно что при этом укладка графа <tex>G</tex> на плоскости будет перенесена на некоторую укладку графа <tex>G</tex> на сфере.
}}
{{Лемма
|about=
II
|statement=
Для любого выделенного ребра планарного графа найдется такая укладка графа на плоскости, что выделенное ребро будет лежать на границе внешней грани.
|proof=
Сначала возьмем укладку графа на сфере. Перенесем эту укладку графа на сфере в укладку на плоскости так как это сделано в лемме II, за точку <tex>N</tex> возьмем точку на сфере не лежащую на ребре, не являющуюся вершиной, и принадлежащую грани на границе которой лежит выделенное ребро. Полученная укладка на плоскости обладает нужным нам свойством.
}}
Докажем утверждение теоремы для одной из компоненты связности графа <tex>G</tex>. Ясно, что имея укладки на плоскости каждой из компонент связности какого-либо графа , мы можем получить укладку на плоскости и всего графа.
Итак пусть граф <tex>G</tex> - связен. Рассмотрим связный под-граф <tex>T</tex> графа компонент реберной двусвязности графа <tex>G</tex>. Согласно [[Граф компонент реберной двусвязности|лемме]] из связности <tex>T</tex> - получаем, что <tex>T</tex> [[Дерево, эквивалентные определения|дерево]]. Докажем индукцией по числу вершин в графе <tex>T</tex>, что под-граф <tex>G'</tex> графа <tex>G</tex> состоящий из компонент реберной двусвязности и мостов графа <tex>G</tex> принадлежащих графа <tex>T</tex> планарен (далее будем говрить, что <tex>G'</tex> соответствует <tex>T</tex>).
'''База индукции.'''
Если <tex>|VT| = 1</tex>, то граф <tex>T</tex> - тривиальный. Его единственная вершина - это компонента реберной двусвязности графа <tex>G</tex>, которая по утверждению теоремы - планарна.
'''Индукционный переход.'''
Пусть утверждение верно для <tex>|VT| < m</tex>. Рассмотрим дерево <tex>T</tex>, для которого <tex>|VT| = m > 1</tex>, и соответствующий <tex>T</tex> под-граф <tex>G'</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>. <tex>G_1</tex> планарен по утверждению теоремы, т.к. блоки графа <tex>G'</tex> совпадают с блоками графа <tex>G</tex>. Далее рассмотрим под-граф <tex>G_2</tex> графа <tex>G'</tex> соответствующий дереву <tex>T\backslash \{G_1\}</tex>. Он планарен по предположению индукции, т.к. <tex>|V(T\backslash \{u\})| = |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_2</tex> на сфере и уложим <tex>G_1</tex> на плоскости так, чтобы ребро <tex>e_1 \in G_1</tex> смежное с <tex>e</tex> в G' оказалось на границе внешней грани (по лемме II это возможно). Обозначим за <tex>u</tex> - вершину из <tex>G_2</tex> инцедентную <tex>e</tex>. Сожмем часть плоскости, содержащую укладку <tex>G_1</tex> так чтобы она вмещалась в одну из граней укладки <tex>G_2</tex> смежную с <tex>u</tex>. Проводя ребро <tex>e</tex> от вершины <tex>u</tex> к инцидентоной ему вершине графа <tex>G_1</tex> мы получаем укладку графа <tex>G'</tex> на сфере, а значит (по лемме I) <tex>G'</tex> планарен, следовательно предположение индукции верно.
Рассматривая в качестве <tex>T</tex> граф компонент реберной двусвязности <tex>G</tex> получаем что <tex>G</tex> - планарен.
}}
