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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (Дмитрий Мурзин переименовал страницу Укладка графа с планарными компонентами реберной двусвязности в [[Укладка графа с планарными ком…)
(не показано 29 промежуточных версий 6 участников)
Строка 1: Строка 1:
 
{{Теорема
 
{{Теорема
|about=об укладке графа с планарными компонентами реберной двусвязности.
+
|about=об укладке графа с планарными компонентами реберной двусвязности
|statement=Если [[Отношение реберной двусвязности|компоненты реберной двусвязности]] (к.р.д.) графа <tex>G</tex> планарны, то и сам граф <tex>G</tex> планарен.
+
|statement=Если [[Отношение реберной двусвязности|компоненты реберной двусвязности]] [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] <tex>G</tex> [[Укладка графа на плоскости|планарны]], то и сам граф <tex>G</tex> планарен.
 
|proof=
 
|proof=
  
Строка 12: Строка 12:
 
|proof=
 
|proof=
  
Рассмотрим укладку графа <tex>G</tex> на сфере. Возьмем на сфере точку <tex>N</tex>, не лежащую на ребре, и не вершину. Выберем на сфере точку <tex>S</tex> противолежащую <tex>N</tex> (<tex>N</tex> и <tex>S</tex> лежат на одном диаметре и при этом не совпадают). Проведем через точку <tex>S</tex> касательную к сфере плоскость. Спроектируем на плоскость все точки сферы, проведя все возможные лучи из точки <tex>N</tex> через точки сферы до пересечения с плоскостью. Ясно, что эта проекция дает укладку графа <tex>G</tex> на плоскости.
+
Рассмотрим укладку графа <tex>G</tex> на сфере. Возьмем на сфере точку <tex>N</tex>, не лежащую на ребре, и не вершину. Выберем на сфере точку <tex>S</tex> противолежащую <tex>N</tex> (<tex>N</tex> и <tex>S</tex> лежат на одном диаметре и при этом не совпадают). Проведем через точку <tex>S</tex> касательную к сфере плоскость. Спроектируем на плоскость все точки сферы, проведя все возможные лучи из точки <tex>N</tex> через точки сферы до пересечения с плоскостью (рис. 1) . Ясно, что эта проекция дает укладку графа <tex>G</tex> на плоскости.
 +
 
 +
[[Файл: Planar_edge_biconnected_1.png|390px|thumb|center|рис. 1. Проекция графа со сферы на плоскость. <tex>S</tex> {{---}} точка касания, <tex>N</tex> {{---}} противоположная точка.]]
 +
 
  
 
Обратно рассмотрим укладку графа <tex>G</tex> на плоскости. Возьмем сферу, которая касается плоскости, и обозначим точку касания за <tex>S</tex>. Противолежащую <tex>S</tex> точку на сфере обозначим за <tex>N</tex>. Проведем все возможные лучи от точек плоскости через точки сферы до точки <tex>N</tex>. Ясно что при этом укладка графа <tex>G</tex> на плоскости будет перенесена на некоторую укладку графа <tex>G</tex> на сфере.
 
Обратно рассмотрим укладку графа <tex>G</tex> на плоскости. Возьмем сферу, которая касается плоскости, и обозначим точку касания за <tex>S</tex>. Противолежащую <tex>S</tex> точку на сфере обозначим за <tex>N</tex>. Проведем все возможные лучи от точек плоскости через точки сферы до точки <tex>N</tex>. Ясно что при этом укладка графа <tex>G</tex> на плоскости будет перенесена на некоторую укладку графа <tex>G</tex> на сфере.
Строка 24: Строка 27:
 
|proof=
 
|proof=
  
Возьмем укладку графа на сфере. Перенесем эту укладку графа на сфере в укладку на плоскости так как это сделано в [[#l1|лемме I]], за точку <tex>N</tex> возьмем точку на сфере, не лежащую на ребре, не являющуюся вершиной и принадлежащую грани на границе которой лежит выделенное ребро. Полученная укладка на плоскости обладает нужным нам свойством.
+
Возьмем укладку графа на сфере. Перенесем эту укладку графа на сфере в укладку на плоскости так как это сделано в [[#l1|лемме I]], за точку <tex>N</tex> возьмем точку на сфере, не лежащую на ребре, не являющуюся вершиной и принадлежащую грани на границе которой лежит выделенное ребро. Полученная укладка на плоскости обладает нужным нам свойством (рис. 2).
 +
 
 +
[[Файл: Planar_edge_biconnected_2.png|220px|thumb|center|рис. 2.]]
 
}}
 
}}
  
Докажем утверждение теоремы для одной из компонент связности графа <tex>G</tex>. Ясно, что имея укладки на плоскости каждой из компонент связности графа , мы можем получить укладку на плоскости и всего графа.
+
Докажем утверждение теоремы для одной из компонент связности графа <tex>G</tex>. Ясно, что имея укладки на плоскости каждой из компонент связности графа, мы можем получить укладку на плоскости и всего графа.
Итак пусть граф <tex>G</tex> связен. Рассмотрим связный подграф <tex>T</tex> графа к.р.д. графа <tex>G</tex>. Из [[Граф компонент реберной двусвязности|леммы]] и из связности <tex>T</tex> получаем, что <tex>T</tex>  &mdash; [[Дерево, эквивалентные определения|дерево]].  
+
Итак пусть граф <tex>G</tex> связен. Рассмотрим связный подграф <tex>T</tex> графа компонент реберной двусвязности графа <tex>G</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 dashed #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> {{---}} тривиальный граф. Его единственная вершина - это компонента реберной двусвязности графа <tex>G</tex>, которая по условию теоремы планарна.
 
</div>
 
</div>
  
 
'''Индукционный переход.'''  
 
'''Индукционный переход.'''  
  
<div style="border:1px solid #000; width:90%; margin: 10px; padding:4px; background-color: #fdfdfd; padding-left:10px;">
+
<div style="border:1px dashed #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>e</tex> &mdash; мост в <tex>G'</tex> инцидентный <tex>G_1</tex> в <tex>T</tex>. <tex>G_1</tex> планарен по утверждению теоремы, т.к. к.р.д. графа <tex>G'</tex> совпадают с к.р.д. графа <tex>G</tex>. Далее рассмотрим подграф <tex>G_2</tex> графа <tex>G'</tex>, соответствующий дереву <tex>T\backslash \{G_1\}</tex>. Поскольку <tex>G_1</tex> &mdash; висячая вершина <tex>T</tex>, то <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> &mdash; компонента реберной двусвязности графа <tex>G'</tex> являющийся висячей вершиной дерева <tex>T</tex>, a <tex>e</tex> &mdash; [[Мост,_эквивалентные_определения|мост]] в <tex>G'</tex> инцидентный <tex>G_1</tex> в <tex>T</tex> (рис. 3). <tex>G_1</tex> планарен по условию теоремы, т.к. компоненты реберной двусвязности графа <tex>G'</tex> совпадают с компонентами реберной двусвязности графа <tex>G</tex>. Далее рассмотрим подграф <tex>G_2</tex> графа <tex>G'</tex>, соответствующий дереву <tex>T\backslash \{G_1\}</tex>. Поскольку <tex>G_1</tex> &mdash; висячая вершина <tex>T</tex>, то <tex>T\backslash \{G_1\}</tex> связен, и, очевидно, также как и <tex>T</tex> является подграфом графа компонент реберной двусвязности <tex>G</tex>. Итак <tex>G_2</tex> планарен по предположению индукции, т.к. <tex>|V(T\backslash \{G_1\})| = |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_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>.
+
[[Файл: Planar_edge_biconnected_3.png|240px|thumb|center|рис. 3. Удаление <tex>G_1</tex> из графа компонент реберной двусвязности]]
  
Уложим <tex>G_2</tex> на сфере и уложим <tex>G_1</tex> на плоскости так, чтобы ребро <tex>e_1 \in G_1</tex> смежное с <tex>e</tex> в G' (если таковое имеется) оказалось на границе внешней грани (по [[#l2|лемме II]] это возможно). Если такого ребра <tex>e_1</tex> не существует, значит <tex>G_1</tex> тривиальный. В таком случае возьмем любую его укладку на плоскости. Обозначим за <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>e</tex> вершине графа <tex>G_1</tex> так, чтобы она не пересекалась с укладками <tex>G_1</tex> и <tex>G_2</tex>. Мы получили укладку графа <tex>G'</tex> на сфере, а значит (по [[#l1|лемме I]]) <tex>G'</tex> планарен, следовательно предположение индукции верно.
+
Уложим <tex>G_2</tex> на сфере и уложим <tex>G_1</tex> на плоскости так, чтобы ребро <tex>e_1 \in G_1</tex> смежное с <tex>e</tex> в G' (если таковое имеется) оказалось на границе внешней грани (по [[#l2|лемме II]] это возможно, рис. 4). Если такого ребра <tex>e_1</tex> не существует, значит компонента реберной двусвязности <tex>G_1</tex> &mdash; тривиальный граф, в таком случае возьмем любую укладку <tex>G_1</tex> на плоскости. Пусть <tex>u\in G_2</tex> {{---}} вершина инцидентная <tex>e</tex>. Сожмем часть плоскости, содержащую укладку <tex>G_1</tex>, так, чтобы она вмещалась в одну из граней укладки <tex>G_2</tex> смежную с <tex>u</tex>. Проведем жорднанову кривую, соответствующую ребру <tex>e</tex>, от вершины <tex>u</tex> к инцидентной <tex>e</tex> вершине графа <tex>G_1</tex> так, чтобы она не пересекалась с укладками <tex>G_1</tex> и <tex>G_2</tex>. Мы получили укладку графа <tex>G'</tex> на сфере, а значит (по [[#l1|лемме I]]) <tex>G'</tex> планарен, следовательно предположение индукции верно.
 +
 
 +
[[Файл: Planar_edge_biconnected_4.png|thumb|220px|center|рис. 4. Укладка <tex>G_1</tex> и <tex>G_2</tex> на сфере]]
 
</div>
 
</div>
  
Рассматривая в качестве <tex>T</tex> граф к.р.д. <tex>G</tex> получаем что <tex>G</tex> - планарен.
+
 
 +
 
 +
Рассматривая в качестве <tex>T</tex> граф компонент реберной двусвязности <tex>G</tex> получаем что <tex>G</tex> - планарен.
 
}}
 
}}
  
'''Замечание.''' Доказательство теоремы непосредственно задает способ укладки графа <tex>G</tex>.
+
'''Замечание.''' В доказательстве теоремы непосредственно указывается способ получения укладки графа <tex>G</tex> из укладок его компонент реберной двусвязности.
 +
==См. также==
 +
*[[Укладка_графа_с_планарными_компонентами_вершинной_двусвязности|Укладка графа с планарными компонентами вершинной двусвязности]]
 +
 
 +
==Источники информации==
  
==Источники==
+
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
  
Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001.
+
* H. Whitney '''Non-separable and planar graphs''' — Trans. Amer. Math. Soc., 1932.
  
H. Whitney - Non-separable and planar graphs - Trans. Amer. Math. Soc., 1932.
+
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Укладки графов ]]

Версия 23:52, 31 января 2019

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

рис. 1. Проекция графа со сферы на плоскость. [math]S[/math] — точка касания, [math]N[/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]

Возьмем укладку графа на сфере. Перенесем эту укладку графа на сфере в укладку на плоскости так как это сделано в лемме I, за точку [math]N[/math] возьмем точку на сфере, не лежащую на ребре, не являющуюся вершиной и принадлежащую грани на границе которой лежит выделенное ребро. Полученная укладка на плоскости обладает нужным нам свойством (рис. 2).

рис. 2.
[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] (рис. 3). [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 \{G_1\})| = |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].

рис. 3. Удаление [math]G_1[/math] из графа компонент реберной двусвязности

Уложим [math]G_2[/math] на сфере и уложим [math]G_1[/math] на плоскости так, чтобы ребро [math]e_1 \in G_1[/math] смежное с [math]e[/math] в G' (если таковое имеется) оказалось на границе внешней грани (по лемме II это возможно, рис. 4). Если такого ребра [math]e_1[/math] не существует, значит компонента реберной двусвязности [math]G_1[/math] — тривиальный граф, в таком случае возьмем любую укладку [math]G_1[/math] на плоскости. Пусть [math]u\in G_2[/math] — вершина инцидентная [math]e[/math]. Сожмем часть плоскости, содержащую укладку [math]G_1[/math], так, чтобы она вмещалась в одну из граней укладки [math]G_2[/math] смежную с [math]u[/math]. Проведем жорднанову кривую, соответствующую ребру [math]e[/math], от вершины [math]u[/math] к инцидентной [math]e[/math] вершине графа [math]G_1[/math] так, чтобы она не пересекалась с укладками [math]G_1[/math] и [math]G_2[/math]. Мы получили укладку графа [math]G'[/math] на сфере, а значит (по лемме I) [math]G'[/math] планарен, следовательно предположение индукции верно.

рис. 4. Укладка [math]G_1[/math] и [math]G_2[/math] на сфере


Рассматривая в качестве [math]T[/math] граф компонент реберной двусвязности [math]G[/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.