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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Теорема |about=Теорема об укладке графа с планарными компонентами вершинной двусвязности. |…»)
 
Строка 12: Строка 12:
 
|proof=
 
|proof=
  
Уложим <tex>G_2</tex> на сфере и уложим <tex>G_1</tex> на плоскости так, чтобы ребро <tex>e_1 \in G_1</tex> смежное с <tex>e</tex> в G' оказалось на границе внешней грани (по [[#l1|лемме II]] это возможно). Обозначим за <tex>u</tex> - вершину из <tex>G_2</tex> инцедентную <tex>e</tex>. Сожмем часть плоскости, содержащую укладку <tex>G_1</tex> так чтобы она вмещалась в одну из граней укладки <tex>G_2</tex> смежную с <tex>u</tex>. Рассмотрим множество <tex>U</tex> вершин смежных с <tex>u_1</tex>. Отбросим ребра инцидентные <tex>u_1</tex>, ясно, что после этого мн-во вершин <tex>U</tex> - лежат на внешней границе <tex>G_1</tex>. Соединим теперь каждую вершину из <tex>U</tex> c <tex>u_2</tex> не пересекающимися жордановыми линиями, так что бы они не задевали укладок <tex>G_1</tex> и <tex>G_2</tex>. Таким образом мы совместили вершины <tex>u_1</tex> и <tex>u_2</tex> в вершине <tex>u_2</tex>, а значит получили укладку графа <tex>G</tex> на сфере, следовательно <tex>G</tex> - планарен.
+
Предварительно заметим, что методика отображения  укладок на сфере в укладки на плоскости и наоборот устанавливается в лемме на странице [[Укладка графа с планарными компонентами реберной двусвязности]]. Уложим <tex>G_2</tex> на сфере и уложим <tex>G_1</tex> на плоскости так, чтобы ребро <tex>e_1 \in G_1</tex> смежное с <tex>e</tex> в G' оказалось на границе внешней грани (по [[#l1|лемме II]] это возможно). Обозначим за <tex>u</tex> - вершину из <tex>G_2</tex> инцедентную <tex>e</tex>. Сожмем часть плоскости, содержащую укладку <tex>G_1</tex> так чтобы она вмещалась в одну из граней укладки <tex>G_2</tex> смежную с <tex>u</tex>. Рассмотрим множество <tex>U</tex> вершин смежных с <tex>u_1</tex>. Отбросим ребра инцидентные <tex>u_1</tex>, ясно, что после этого множество вершин <tex>U</tex> лежит на внешней границе <tex>G_1</tex>. Соединим теперь каждую вершину из <tex>U</tex> c <tex>u_2</tex> не пересекающимися жордановыми линиями, так что бы они не задевали укладок <tex>G_1</tex> и <tex>G_2</tex>. Таким образом мы совместили вершины <tex>u_1</tex> и <tex>u_2</tex> в вершине <tex>u_2</tex>, а значит получили укладку графа <tex>G</tex> на сфере, следовательно <tex>G</tex> - планарен.
 
}}
 
}}
  
 
Докажем утверждение теоремы для одной из компоненты связности графа <tex>G</tex>. Ясно, что имея укладки на плоскости каждой из компонент связности какого-либо графа , мы можем получить укладку на плоскости и всего графа.
 
Докажем утверждение теоремы для одной из компоненты связности графа <tex>G</tex>. Ясно, что имея укладки на плоскости каждой из компонент связности какого-либо графа , мы можем получить укладку на плоскости и всего графа.
Итак пусть граф <tex>G</tex> связен. Если <tex>G = K_1</tex>, то <tex>G</tex> очевидно планерен, поэтому предположим, что <tex>|EG| \ge 1</tex> , а значит имеется по-крайней мере один блок. Рассмотрим связный подграф <tex>T</tex> графа блоков и точек сочленений графа <tex>G</tex> такой, все висячие вершины - блоки графа <tex>G</tex>. Из [[Граф блоков-точек сочленения|леммы]] и из связности <tex>T</tex> - получаем, что <tex>T</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>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>).
  
 
'''База индукции.'''  
 
'''База индукции.'''  
 
 
<div style="border:1px solid #000; width:90%; margin: 10px; padding:4px; background-color: #fdfdfd; padding-left:10px;">
 
<div style="border:1px solid #000; width:90%; margin: 10px; padding:4px; background-color: #fdfdfd; padding-left:10px;">
Если <tex>|VT| = 1</tex>, то граф <tex>T</tex> - тривиальный. Его единственная вершина - это блок графа <tex>G</tex>, который по утверждению теоремы - планарен.
+
Если <tex>|VT| = 1</tex>, то граф <tex>T</tex> тривиальный. Его единственная вершина &mdash; это блок графа <tex>G</tex>, который по утверждению теоремы планарен.
 
</div>
 
</div>
  
Строка 29: Строка 28:
  
 
<div style="border:1px solid #000; width:90%; margin: 10px; padding:4px; background-color: #fdfdfd; padding-left:10px;">
 
<div style="border:1px solid #000; width:90%; margin: 10px; padding:4px; background-color: #fdfdfd; padding-left:10px;">
Пусть утверждение верно для <tex>|VT| < m</tex>. Рассмотрим <tex>T</tex>, для которого <tex>|VT| = m > 1</tex>, и соответствующий <tex>T</tex> подграф <tex>G'</tex> графа <tex>G</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'</tex> планарен.
 +
 
 +
Положим <tex>G_1</tex> &mdash; это блок графа <tex>G'</tex> являющийся висячей вершиной дерева <tex>T</tex>, a <tex>v</tex> &mdash; т.с. в <tex>G'</tex> смежная с <tex>G_1</tex> в <tex>T</tex>. <tex>G_1</tex> планарен по утверждению теоремы, т.к. блоки графа <tex>G'</tex> совпадают с блоками графа <tex>G</tex>. Заметим, что <tex>deg v > 0</tex>, т.к. <tex>v</tex> - т.с., следовательно не висячая. Рассмотрим два случая:
  
Положим <tex>G_1</tex> - блок графа <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 > 0</tex>, т.к. <tex>v</tex> - т.с., следовательно не висячая. Рассмотрим два случая:
+
#<tex>deg(v) = 2</tex> в <tex>T</tex>. Обозначим за <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. v}</tex> по очереди были висячими вершинами <tex>T</tex> и <tex>T\backslash {u}</tex>.
# <tex>deg v = 2</tex> в <tex>T</tex>. Обозначим за <tex>T'</tex> <tex>T\backslash {u,v}</tex>. Поскольку степень ни одной из т.с. <tex>G'</tex> принадлежащих  <tex>T</tex> (кроме удаленной <tex>v</tex>) не уменьшилась, то ни одна из тех т.с. не превратиться в лист в <tex>T'</tex>. Заметим, что <tex>VT' = VT - 2 = m - 2 < m</tex>. Заметим также, что <tex>T'</tex> - связен, т.к. {u. v}  по очереди были висячими вершинами <tex>T</tex> и <tex>T\backslash {u}</tex>.
+
#<tex>deg (v) > 2</tex> в <tex>T</tex>. Обозначим за <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>
# <tex>deg v > 2</tex> в <tex>T</tex>. Обозначим за <tex>T'</tex> <tex>T\backslash {u}</tex>. Поскольку степень ни одной из т.с. <tex>G'</tex> принадлежащих  <tex>T</tex> (кроме кроме <tex>v</tex> - для нее степень уменьшилась ровно на 1) не уменьшилась ни одна из тех т.с. не превратиться в лист в <tex>T'</tex>. <tex>deg v >= 2</tex> в <tex>T'</tex>, а значит и <tex>v</tex> не является листом в <tex>T'</tex>. Заметим, что <tex>VT' = VT - 1 = m - 1 < m</tex>. Заметим также, что <tex>T'</tex> - связен, т.к. {u}  была висячей вершиной в <tex>T</tex>.
 
   
 
Рассмотрим подграф <tex>G_2</tex> графа <tex>G'</tex> соответствующий дереву <tex>T'</tex>. Поскольку T' - связен, то <tex>T\backslash \{G_1\}</tex> связен, и очевидно также как и <tex>T</tex> является подграфом графа блоков и точек сочленений <tex>G</tex>. А значит <tex>G_2</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'</tex> соответствующий дереву <tex>T'</tex>. Поскольку T' - связен, степени вершин в <tex>T'</tex> соответствующих т.с. графа <tex>G'</tex> удовлетворяют предположению индукции, и очевидно также как и <tex>T</tex> является подграфом графа блоков и точек сочленений <tex>G</tex>, получим, что <tex>G_2</tex> планарен по предположению индукции, т.к. <tex>VT' < m</tex>.  
  
Уложим <tex>G_2</tex> на сфере и уложим <tex>G_1</tex> на плоскости так, чтобы ребро <tex>e_1 \in G_1</tex> смежное с <tex>e</tex> в G' оказалось на границе внешней грани (по [[#l1|лемме 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> на сфере, а значит (по [[#l1|лемме I]]) <tex>G'</tex> планарен, следовательно предположение индукции верно.
+
Из определения ребер дерева блоков и точек сочленений получаем, что графы <tex>G_1</tex> и <tex>G_2</tex> содержат единственную общую точку - точку сочленения <tex>v</tex>. Поскольку множество блоков <tex>G'</tex> принадлежащих <tex>T</tex> состоит из <tex>G_1</tex> и множества блоков <tex>T'</tex>, то <tex>G' = \{G_1\}\cup \{G_2\}</tex>. <tex>G_1, G_2, G'</tex> удовлетворяют условию [[#l1|леммы I]], поэтому получим укладку <tex>G</tex> из укладок <tex>G_1, G_2</tex> так как это сделано в доказательстве леммы. получаем <tex>G'</tex> - планарен. А значит предположение индукции - верно.
 
</div>
 
</div>
  
Рассматривая в качестве <tex>T</tex> граф компонент реберной двусвязности <tex>G</tex> получаем что <tex>G</tex> - планарен.
+
Рассматривая в качестве <tex>T</tex> граф <tex>T_G</tex> блоков и точек сочленений <tex>G</tex>. По [[Граф блоков-точек сочленения|лемме]] <tex>T_G</tex> - дерево, следовательно каждая его вершина имеет степень как минимум <tex>1</tex>. Поскольку граф <tex>G<tex> содержит хотя бы один блок. Если это единственный блок, то <tex>T_G</tex> не содержит ни одной точки сочленения. Если граф <tex>G</tex> содержит хотя бы <tex>2</tex> блока и, следовательно, хотя бы одну точку сочленения,  то <tex>T_G</tex> &mdash; дерево, содержащее хотя бы одно ребро. Поскольку в графе блоков и точек сочленений точки сочленений не могут быть висячими вершинами, то каждая из т.с. графа <tex>G</tex> принадлежащих <tex>T_G</tex> имеет степень как минимум <tex>2</tex>. планарен. Получаем, что <tex>T_G</tex> удовлетворяет условиям на <tex>T</tex> из предположения индукции, а значит <tex>G</tex> планарен.
 
}}
 
}}
  

Версия 11:42, 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]
Предварительно заметим, что методика отображения укладок на сфере в укладки на плоскости и наоборот устанавливается в лемме на странице Укладка графа с планарными компонентами реберной двусвязности. Уложим [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]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]

Источники

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

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