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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 33: Строка 33:
 
Положим <tex>G_1</tex> &mdash; это блок графа <tex>G'</tex> являющийся висячей вершиной дерева <tex>T</tex> (вспомним, что в дереве, в котором более одной вершины, всегда есть есть висячие вершины, и то, что висячими вершинами в графе блоков и т.с. не могут быть т.с.), a <tex>v</tex> {{---}} т.с. в <tex>G'</tex> смежная с <tex>G_1</tex> в <tex>T</tex>. <tex>G_1</tex> планарен по утверждению теоремы, т.к. блоки графа <tex>G'</tex> совпадают с блоками графа <tex>G</tex>. Заметим, что <tex>deg(v) > 1</tex>, т.к. <tex>v</tex> {{---}} т.с., следовательно не висячая. Рассмотрим два случая:
 
Положим <tex>G_1</tex> &mdash; это блок графа <tex>G'</tex> являющийся висячей вершиной дерева <tex>T</tex> (вспомним, что в дереве, в котором более одной вершины, всегда есть есть висячие вершины, и то, что висячими вершинами в графе блоков и т.с. не могут быть т.с.), a <tex>v</tex> {{---}} т.с. в <tex>G'</tex> смежная с <tex>G_1</tex> в <tex>T</tex>. <tex>G_1</tex> планарен по утверждению теоремы, т.к. блоки графа <tex>G'</tex> совпадают с блоками графа <tex>G</tex>. Заметим, что <tex>deg(v) > 1</tex>, т.к. <tex>v</tex> {{---}} т.с., следовательно не висячая. Рассмотрим два случая:
  
#<tex>deg(v) = 2</tex> в <tex>T</tex> (рис. 2). Обозначим за <tex>T'</tex> <tex>T\backslash \{u,v\}</tex>. Поскольку степень ни одной из т.с. <tex>G'</tex> принадлежащих  <tex>T</tex> (кроме удаленной <tex>v</tex>) не уменьшилась, значит <tex>T'</tex> удовлетворяет условиям на <tex>T</tex> из предположения индукции. Заметим, что <tex>VT' = VT - 2 = m - 2 < m</tex>. Заметим также, что <tex>T'</tex> связен, т.к. <tex>u</tex> и <tex>v</tex>  по очереди были висячими вершинами <tex>T</tex> и <tex>T\backslash \{u\}</tex>.[[Файл: Planar vertex biconnected 2.png|300px|center|thumb|рис. 2. Красные {{---}} точки сочленений. Голубые {{---}} блоки.]]
+
#<tex>deg(v) = 2</tex> в <tex>T</tex> (рис. 2). Обозначим за <tex>T'</tex> <tex>T\backslash \{u,v\}</tex>. Поскольку степень ни одной из т.с. <tex>G'</tex> принадлежащих  <tex>T</tex> (кроме удаленной <tex>v</tex>) не уменьшилась, значит <tex>T'</tex> удовлетворяет условиям на <tex>T</tex> из предположения индукции. Заметим, что <tex>VT' = VT - 2 = m - 2 < m</tex>. Заметим также, что <tex>T'</tex> связен, т.к. <tex>u</tex> и <tex>v</tex>  по очереди были висячими вершинами <tex>T</tex> и <tex>T\backslash \{u\}</tex>.[[Файл: Planar vertex biconnected 2.png|270px|center|thumb|рис. 2. Красные {{---}} точки сочленений. Голубые {{---}} блоки.]]
#<tex>deg (v) > 2</tex> в <tex>T</tex> (рис. 3). Обозначим за <tex>T'</tex> <tex>T\backslash \{u\}</tex>. Поскольку степень ни одной из т.с. <tex>G'</tex> принадлежащих  <tex>T</tex> (кроме <tex>v</tex>, для нее степень уменьшилась ровно на <tex>1</tex>) не уменьшилась, а для вершины <tex>v</tex> в <tex>T'</tex> верно, что <tex>deg(v) >= 2</tex>, то <tex>T'</tex> удовлетворяет условиям на <tex>T</tex> из предположения индукции. Заметим, что <tex>VT' = VT - 1 = m - 1 < m</tex>. Заметим также, что <tex>T'</tex> связен, т.к. <tex>u</tex>  была висячей вершиной в <tex>T</tex>.[[Файл: Planar vertex biconnected 3.png|300px|center|thumb|рис. 3. Красные {{---}} точки сочленений. Голубые {{---}} блоки.]]
+
#<tex>deg (v) > 2</tex> в <tex>T</tex> (рис. 3). Обозначим за <tex>T'</tex> <tex>T\backslash \{u\}</tex>. Поскольку степень ни одной из т.с. <tex>G'</tex> принадлежащих  <tex>T</tex> (кроме <tex>v</tex>, для нее степень уменьшилась ровно на <tex>1</tex>) не уменьшилась, а для вершины <tex>v</tex> в <tex>T'</tex> верно, что <tex>deg(v) >= 2</tex>, то <tex>T'</tex> удовлетворяет условиям на <tex>T</tex> из предположения индукции. Заметим, что <tex>VT' = VT - 1 = m - 1 < m</tex>. Заметим также, что <tex>T'</tex> связен, т.к. <tex>u</tex>  была висячей вершиной в <tex>T</tex>.[[Файл: Planar vertex biconnected 3.png|270px|center|thumb|рис. 3. Красные {{---}} точки сочленений. Голубые {{---}} блоки.]]
  
 
Рассмотрим подграф <tex>G_2</tex> графа <tex>G'</tex> соответствующий дереву <tex>T'</tex>. Поскольку <tex>T'</tex> связен, степени вершин в <tex>T'</tex> соответствующих т.с. графа <tex>G'</tex> удовлетворяют предположению индукции и, очевидно, также как и <tex>T</tex> граф <tex>T'</tex> является подграфом графа блоков и точек сочленений <tex>G</tex>, получим, что <tex>G_2</tex> планарен по предположению индукции, т.к. <tex>VT' < m</tex>.  
 
Рассмотрим подграф <tex>G_2</tex> графа <tex>G'</tex> соответствующий дереву <tex>T'</tex>. Поскольку <tex>T'</tex> связен, степени вершин в <tex>T'</tex> соответствующих т.с. графа <tex>G'</tex> удовлетворяют предположению индукции и, очевидно, также как и <tex>T</tex> граф <tex>T'</tex> является подграфом графа блоков и точек сочленений <tex>G</tex>, получим, что <tex>G_2</tex> планарен по предположению индукции, т.к. <tex>VT' < m</tex>.  

Версия 10:39, 24 апреля 2012

Теорема (об укладке графа с планарными компонентами вершинной двусвязности):
Если компоненты вершинной двусвязности графа [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] (рис. 1). Таким образом мы совместили вершины [math]v_1[/math] и [math]v_2[/math] в вершине [math]v_2[/math], а значит получили укладку графа [math]G[/math] на сфере, следовательно [math]G[/math] - планарен.

рис. 1.
[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 1[/math], т.к. [math]v[/math] — т.с., следовательно не висячая. Рассмотрим два случая:

  1. [math]deg(v) = 2[/math] в [math]T[/math] (рис. 2). Обозначим за [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[/math] и [math]v[/math] по очереди были висячими вершинами [math]T[/math] и [math]T\backslash \{u\}[/math].
    рис. 2. Красные — точки сочленений. Голубые — блоки.
  2. [math]deg (v) \gt 2[/math] в [math]T[/math] (рис. 3). Обозначим за [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].
    рис. 3. Красные — точки сочленений. Голубые — блоки.

Рассмотрим подграф [math]G_2[/math] графа [math]G'[/math] соответствующий дереву [math]T'[/math]. Поскольку [math]T'[/math] связен, степени вершин в [math]T'[/math] соответствующих т.с. графа [math]G'[/math] удовлетворяют предположению индукции и, очевидно, также как и [math]T[/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[/math] и [math]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[/math] содержит хотя бы один блок. Если это единственный блок, то [math]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. — 288 с. — ISBN 5-93972-076-5
  • H. Whitney Non-separable and planar graphs — Trans. Amer. Math. Soc., 1932.