Укладка графа с планарными компонентами рёберной двусвязности

Теорема (Теорема об укладке графа с планарными компонентами реберной двусвязности.):

Если компоненты реберной двусвязности графа [math]G[/math] планарны, то и сам граф [math]G[/math] планарен.

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

[math]\triangleright[/math]

Докажем для начала ряд вспомогательных лемм. Лемма (I): Граф [math]G[/math] планарен тогда и только тогда когда он обладает укладкой на сфере Доказательство: [math]\triangleright[/math] Рассмотрим укладку графа [math]G[/math] на сфере. Возьмем на сфере точку [math]N[/math] не лежащую на ребре и не вершину. Выберем на сфере точку [math]S[/math] противолежащую [math]N[/math] ([math]N[/math] и [math]S[/math] лежат на одном диаметре и не совпадают). Проведем через точку [math]S[/math] касательную к сфере плоскость. Спроектируем на плоскость все точки сферы, проведя всевозможные лучи из точки [math]N[/math] через точки сферы до плоскости. Ясно, что эта проекция дает укладку графа [math]G[/math] на плоскости. Обратно рассмотрим укладку графа [math]G[/math] на плоскости. Возьмем сферу, которая касается плоскости, и обозначим точку касания за [math]S[/math]. Противолежащую [math]S[/math] точку на сфере обозначим за [math]N[/math]. Проведем все возможные лучи от точек плоскости через точки сферы до точки [math]N[/math]. Ясно что при этом укладка графа [math]G[/math] на плоскости будет перенесена на некоторую укладку графа [math]G[/math] на сфере. [math]\triangleleft[/math] Лемма (II): Для любого выделенного ребра планарного графа найдется такая укладка графа на плоскости, что выделенное ребро будет лежать на границе внешней грани. Доказательство: [math]\triangleright[/math] Сначала возьмем укладку графа на сфере. Перенесем эту укладку графа на сфере в укладку на плоскости так как это сделано в лемме II, за точку [math]N[/math] возьмем точку на сфере не лежащую на ребре, не являющуюся вершиной, и принадлежащую грани на границе которой лежит выделенное ребро. Полученная укладка на плоскости обладает нужным нам свойством. [math]\triangleleft[/math] Докажем утверждение теоремы для одной из компоненты связности графа [math]G[/math]. Ясно, что имея укладки на плоскости каждой из компонент связности какого-либо графа , мы можем получить укладку на плоскости и всего графа. Итак пусть граф [math]G[/math] связен. Рассмотрим связный подграф [math]T[/math] графа компонент реберной двусвязности графа [math]G[/math]. Из леммы и из связности [math]T[/math] - получаем, что [math]T[/math] - дерево. Докажем индукцией по числу вершин в графе [math]T[/math], что подграф [math]G'[/math] графа [math]G[/math] состоящий из компонент реберной двусвязности и мостов графа [math]G[/math] принадлежащих графу [math]T[/math] планарен (далее будем говрить, что [math]G'[/math] соответствует [math]T[/math]). База индукции. Если [math]|VT| = 1[/math], то граф [math]T[/math] - тривиальный. Его единственная вершина - это компонента реберной двусвязности графа [math]G[/math], которая по утверждению теоремы - планарна. Индукционный переход. Пусть утверждение верно для [math]|VT| \lt m[/math]. Рассмотрим [math]T[/math], для которого [math]|VT| = m \gt 1[/math], и соответствующий [math]T[/math] подграф [math]G'[/math] графа [math]G[/math]. Докажем, что [math]G'[/math] - планарен. Положим [math]G_1[/math] - блок графа [math]G'[/math] являющийся висячей вершиной дерева [math]T[/math], a [math]e[/math] - мост в [math]G'[/math] инцидентный [math]G_1[/math] в [math]T[/math]. [math]G_1[/math] планарен по утверждению теоремы, т.к. блоки графа [math]G'[/math] совпадают с блоками графа [math]G[/math]. Далее рассмотрим подграф [math]G_2[/math] графа [math]G'[/math] соответствующий дереву [math]T\backslash \{G_1\}[/math]. Поскольку [math]G_1[/math] - висячая вершина [math]T[/math], то [math]T\backslash \{G_1\}[/math] связен, и очевидно также как и [math]T[/math] является подграфом графа компонент реберной двусвязности [math]G[/math]. А значит [math]G_2[/math] планарен по предположению индукции, т.к. [math]|V(T\backslash \{u\})| = |VT| - 1 = m - 1 \lt m[/math]. Из определения ребер дерева компонент реберной двусвязности получаем, что графы [math]G_1[/math] и [math]G_2[/math] соединены в графе [math]G'[/math] единственным мостом [math]e \in G'[/math] инцидентным блоку [math]G_1[/math] в дереве [math]T[/math]. Поскольку [math]T = \{G_1\}\cup e\cup \{G_2\}[/math], то и [math]G' = \{G_1\}\cup e\cup \{G_2\}[/math]. Покажем как из укладок [math]G_1[/math] и [math]G_2[/math] получить укладку [math]G'[/math]. Уложим [math]G_2[/math] на сфере и уложим [math]G_1[/math] на плоскости так, чтобы ребро [math]e_1 \in G_1[/math] смежное с [math]e[/math] в G' оказалось на границе внешней грани (по лемме II это возможно). Обозначим за [math]u[/math] - вершину из [math]G_2[/math] инцедентную [math]e[/math]. Сожмем часть плоскости, содержащую укладку [math]G_1[/math] так чтобы она вмещалась в одну из граней укладки [math]G_2[/math] смежную с [math]u[/math]. Проводя ребро [math]e[/math] от вершины [math]u[/math] к инцидентоной ему вершине графа [math]G_1[/math] мы получаем укладку графа [math]G'[/math] на сфере, а значит (по лемме I) [math]G'[/math] планарен, следовательно предположение индукции верно. Рассматривая в качестве [math]T[/math] граф компонент реберной двусвязности [math]G[/math] получаем что [math]G[/math] - планарен.

[math]\triangleleft[/math]

Источники

Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001.

H. Whitney - Non-separable and planar graphs - Trans. Amer. Math. Soc., 1932.