|
Докажем вспомогательную лемму.
| Лемма (I): |
Пусть графы [math]G_1[/math] и [math]G_2[/math] планарны. Граф [math]G[/math] получается из [math]G_1[/math] и [math]G_2[/math] совмещением вершин [math]v_1 \in G_1[/math] и [math]v_2 \in G_2[/math]. Тогда [math]G[/math] планарен. |
| Доказательство: |
| [math]\triangleright[/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]U[/math] вершин смежных с [math]u_1[/math]. Отбросим ребра инцидентные [math]u_1[/math], ясно, что после этого мн-во вершин [math]U[/math] - лежат на внешней границе [math]G_1[/math]. Соединим теперь каждую вершину из [math]U[/math] c [math]u_2[/math] не пересекающимися жордановыми линиями, так что бы они не задевали укладок [math]G_1[/math] и [math]G_2[/math]. Таким образом мы совместили вершины [math]u_1[/math] и [math]u_2[/math] в вершине [math]u_2[/math], а значит получили укладку графа [math]G[/math] на сфере, следовательно [math]G[/math] - планарен. | | [math]\triangleleft[/math] |
Докажем утверждение теоремы для одной из компоненты связности графа [math]G[/math]. Ясно, что имея укладки на плоскости каждой из компонент связности какого-либо графа , мы можем получить укладку на плоскости и всего графа.
Итак пусть граф [math]G[/math] связен. Если [math]G = K_1[/math], то [math]G[/math] очевидно планерен, поэтому предположим, что [math]|EG| \ge 1[/math] , а значит имеется по-крайней мере один блок. Рассмотрим связный подграф [math]T[/math] графа блоков и точек сочленений графа [math]G[/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]v[/math] - т.с. в [math]G'[/math] смежная с [math]G_1[/math] в [math]T[/math]. [math]G_1[/math] планарен по утверждению теоремы, т.к. блоки графа [math]G'[/math] совпадают с блоками графа [math]G[/math]. Заметим, что [math]deg v \gt 0[/math], т.к. [math]v[/math] - т.с., следовательно не висячая. Рассмотрим два случая:
- [math]deg v = 2[/math] в [math]T[/math]. Обозначим за [math]T'[/math] [math]T\backslash {u,v}[/math]. Поскольку степень ни одной из т.с. [math]G'[/math] принадлежащих [math]T[/math] (кроме удаленной [math]v[/math]) не уменьшилась, то ни одна из тех т.с. не превратиться в лист в [math]T'[/math]. Заметим, что [math]VT' = VT - 2 = m - 2 \lt m[/math]. Заметим также, что [math]T'[/math] - связен, т.к. {u. v} по очереди были висячими вершинами [math]T[/math] и [math]T\backslash {u}[/math].
- [math]deg v \gt 2[/math] в [math]T[/math]. Обозначим за [math]T'[/math] [math]T\backslash {u}[/math]. Поскольку степень ни одной из т.с. [math]G'[/math] принадлежащих [math]T[/math] (кроме кроме [math]v[/math] - для нее степень уменьшилась ровно на 1) не уменьшилась ни одна из тех т.с. не превратиться в лист в [math]T'[/math]. [math]deg v \gt = 2[/math] в [math]T'[/math], а значит и [math]v[/math] не является листом в [math]T'[/math]. Заметим, что [math]VT' = VT - 1 = m - 1 \lt m[/math]. Заметим также, что [math]T'[/math] - связен, т.к. {u} была висячей вершиной в [math]T[/math].
Рассмотрим подграф [math]G_2[/math] графа [math]G'[/math] соответствующий дереву [math]T'[/math]. Поскольку T' - связен, то [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] - планарен. |
