Укладка графа с планарными компонентами вершинной двусвязности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Теорема
 
{{Теорема
 
|about=об укладке графа с планарными компонентами вершинной двусвязности
 
|about=об укладке графа с планарными компонентами вершинной двусвязности
|statement=Если [[Отношение вершинной двусвязности|компоненты вершинной двусвязности]] графа <tex>G</tex> планарны, то и сам граф <tex>G</tex> планарен.
+
|statement=Если [[Отношение вершинной двусвязности|компоненты вершинной двусвязности]] [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] <tex>G</tex> [[Укладка графа на плоскости|планарны]], то и сам граф <tex>G</tex> планарен.
 
|proof=
 
|proof=
  
Строка 15: Строка 15:
 
}}
 
}}
  
Докажем утверждение теоремы для одной из компоненты связности графа <tex>G</tex>. Ясно, что имея укладки на плоскости каждой из компонент связности какого-либо графа , мы можем получить укладку на плоскости и всего графа.
+
Докажем утверждение теоремы для одной из компоненты связности графа <tex>G</tex>. Ясно, что имея укладки на плоскости каждой из компонент связности графа, мы можем получить укладку на плоскости и всего графа.
Итак пусть граф <tex>G</tex> связен. Если <tex>G = K_1</tex>, то <tex>G</tex> очевидно планерен, поэтому предположим, что <tex>|EG| \ge 1</tex> , а значит имеется по-крайней мере один блок в <tex>G</tex>. Рассмотрим связный подграф <tex>T</tex> графа блоков и точек сочленений графа <tex>G</tex> такой, что <tex>\forall v</tex> &mdash; т.с. <tex>G</tex> имеем <tex>deg(v) \ge 2</tex>. Из [[Граф блоков-точек сочленения|леммы]] и из связности <tex>T</tex> - получаем, что <tex>T</tex> &mdash; двудольное [[Дерево, эквивалентные определения|дерево]].  
+
Итак пусть граф <tex>G</tex> связен. Если <tex>G = K_1</tex>, то <tex>G</tex> очевидно планерен, поэтому предположим, что <tex>|EG| \ge 1</tex> , а значит имеется по-крайней мере один блок в <tex>G</tex>. Рассмотрим связный подграф <tex>T</tex> графа блоков и точек сочленений графа <tex>G</tex> такой, что <tex>\forall v</tex> - т.с. <tex>G</tex> имеем <tex>deg(v) \ge 2</tex>. Из [[Граф блоков-точек сочленения#lemma1|леммы]] и из связности <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>).
 
Докажем индукцией по числу вершин в графе <tex>T</tex>, что подграф <tex>G'</tex> графа <tex>G</tex> состоящий из блоков графа <tex>G</tex> принадлежащих графу <tex>T</tex> планарен (далее будем говрить, что <tex>G'</tex> соответствует <tex>T</tex>).

Версия 20:55, 21 октября 2010

Теорема (об укладке графа с планарными компонентами вершинной двусвязности):
Если компоненты вершинной двусвязности графа [math]G[/math] планарны, то и сам граф [math]G[/math] планарен.
Доказательство:
[math]\triangleright[/math]

Докажем вспомогательную лемму.

Лемма (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]
Предварительно заметим, что в доказательстве используются утверждения лемм I и II из статьи Укладка графа с планарными компонентами реберной двусвязности. Итак, уложим [math]G_2[/math] на сфере и уложим [math]G_1[/math] на плоскости так, чтобы ребро [math]e_1 \in G_1[/math] смежное с [math]v_1[/math] (если таковое имеется) оказалось на границе внешней грани (по лемме II это возможно). Если такого ребра [math]e_1[/math] не существует, значит вершина [math]v_1[/math] изолирована, в таком случае возьмем любую укладку [math]G_1[/math] на плоскости и переместим точку, соответствующую [math]v_1[/math] во внешнюю грань. Сожмем часть плоскости, содержащую укладку [math]G_1[/math] так, чтобы она вмещалась в одну из граней укладки [math]G_2[/math] смежную с [math]v_1[/math]. Рассмотрим множество [math]U[/math] вершин смежных с [math]v_1[/math]. Уберем кривые, соответствующие ребрам, инцидентным [math]v_1[/math]. Ясно, что после этого множество вершин [math]U[/math] лежит на внешней границе укладки [math]G_1[/math]. Соединим теперь каждую вершину из [math]U[/math] c [math]v_2[/math] непересекающимися жордановыми линиями так, чтобы они не задевали укладок [math]G_1[/math] и [math]G_2[/math]. Таким образом мы совместили вершины [math]v_1[/math] и [math]v_2[/math] в вершине [math]v_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]G[/math]. Рассмотрим связный подграф [math]T[/math] графа блоков и точек сочленений графа [math]G[/math] такой, что [math]\forall v[/math] - т.с. [math]G[/math] имеем [math]deg(v) \ge 2[/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] - т.с., следовательно не висячая. Рассмотрим два случая:

  1. [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]T[/math] из предположения индукции. Заметим, что [math]VT' = VT - 2 = m - 2 \lt m[/math]. Заметим также, что [math]T'[/math] связен, т.к. [math]{u. v}[/math] по очереди были висячими вершинами [math]T[/math] и [math]T\backslash {u}[/math].
  2. [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], для нее степень уменьшилась ровно на [math]1[/math]) не уменьшилась, а для вершины [math]v[/math] в [math]T'[/math] верно, что [math]deg v \gt = 2[/math], то [math]T'[/math] удовлетворяет условиям на [math]T[/math] из предположения индукции. Заметим, что [math]VT' = VT - 1 = m - 1 \lt m[/math]. Заметим также, что [math]T'[/math] связен, т.к. [math]u[/math] была висячей вершиной в [math]T[/math]

Рассмотрим подграф [math]G_2[/math] графа [math]G'[/math] соответствующий дереву [math]T'[/math]. Поскольку T' - связен, степени вершин в [math]T'[/math] соответствующих т.с. графа [math]G'[/math] удовлетворяют предположению индукции, и очевидно также как и [math]T[/math] является подграфом графа блоков и точек сочленений [math]G[/math], получим, что [math]G_2[/math] планарен по предположению индукции, т.к. [math]VT' \lt m[/math].

Из определения ребер дерева блоков и точек сочленений получаем, что графы [math]G_1[/math] и [math]G_2[/math] содержат единственную общую точку - точку сочленения [math]v[/math]. Поскольку множество блоков [math]G'[/math] принадлежащих [math]T[/math] состоит из [math]G_1[/math] и множества блоков [math]T'[/math], то [math]G' = \{G_1\}\cup \{G_2\}[/math]. [math]G_1, G_2, G'[/math] удовлетворяют условию леммы I, поэтому получим укладку [math]G[/math] из укладок [math]G_1, G_2[/math] так как это сделано в доказательстве леммы. получаем [math]G'[/math] - планарен. А значит предположение индукции - верно.

Рассматривая в качестве [math]T[/math] граф [math]T_G[/math] блоков и точек сочленений [math]G[/math]. По лемме [math]T_G[/math] - дерево, следовательно каждая его вершина имеет степень как минимум [math]1[/math]. Поскольку граф [math]G\lt tex\gt содержит хотя бы один блок. Если это единственный блок, то \lt tex\gt T_G[/math] не содержит ни одной точки сочленения. Если граф [math]G[/math] содержит хотя бы [math]2[/math] блока и, следовательно, хотя бы одну точку сочленения, то [math]T_G[/math] — дерево, содержащее хотя бы одно ребро. Поскольку в графе блоков и точек сочленений точки сочленений не могут быть висячими вершинами, то каждая из т.с. графа [math]G[/math] принадлежащих [math]T_G[/math] имеет степень как минимум [math]2[/math]. планарен. Получаем, что [math]T_G[/math] удовлетворяет условиям на [math]T[/math] из предположения индукции, а значит [math]G[/math] планарен.
[math]\triangleleft[/math]

Замечание. Доказательство теоремы непосредственно задает способ укладки графа [math]G[/math].

Источники

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

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