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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 16 промежуточных версий 7 участников)
Строка 12: Строка 12:
 
|proof=
 
|proof=
  
Предварительно заметим, что в доказательстве используются утверждения [[Укладка графа с планарными компонентами реберной двусвязности#l1|леммы I]] и [[Укладка графа с планарными компонентами реберной двусвязности#l2|леммы II]] из статьи [[Укладка графа с планарными компонентами реберной двусвязности]]. Итак, уложим <tex>G_2</tex> на сфере и уложим <tex>G_1</tex> на плоскости так, чтобы ребро <tex>e_1 \in G_1</tex> смежное с <tex>v_1</tex> (если таковое имеется) оказалось на границе внешней грани (по [[#l2|лемме II]] это возможно). Если такого ребра <tex>e_1</tex> не существует, значит вершина <tex>v_1</tex> изолирована, в таком случае возьмем любую укладку <tex>G_1</tex> на плоскости и переместим точку, соответствующую <tex>v_1</tex> во внешнюю грань. Сожмем часть плоскости, содержащую укладку <tex>G_1</tex> так, чтобы она вмещалась в одну из граней укладки <tex>G_2</tex> смежную с <tex>v_1</tex>. Рассмотрим множество <tex>U</tex> вершин смежных с <tex>v_1</tex>. Уберем кривые, соответствующие ребрам, инцидентным <tex>v_1</tex>. Ясно, что после этого множество вершин <tex>U</tex> лежит на внешней границе укладки <tex>G_1</tex>. Соединим теперь каждую вершину из <tex>U</tex> c <tex>v_2</tex> непересекающимися жордановыми линиями так, чтобы они не задевали укладок <tex>G_1</tex> и <tex>G_2</tex>. Таким образом мы совместили вершины <tex>v_1</tex> и <tex>v_2</tex> в вершине <tex>v_2</tex>, а значит получили укладку графа <tex>G</tex> на сфере, следовательно <tex>G</tex> - планарен.
+
Предварительно заметим, что в доказательстве используются утверждения [[Укладка графа с планарными компонентами реберной двусвязности#l1|леммы I]] и [[Укладка графа с планарными компонентами реберной двусвязности#l2|леммы II]] из статьи [[Укладка графа с планарными компонентами реберной двусвязности]]. Итак, уложим <tex>G_2</tex> на сфере и уложим <tex>G_1</tex> на плоскости так, чтобы ребро <tex>e_1 \in G_1</tex> смежное с <tex>v_1</tex> (если таковое имеется) оказалось на границе внешней грани (по [[#l2|лемме II]] это возможно). Если такого ребра <tex>e_1</tex> не существует, значит вершина <tex>v_1</tex> изолирована, в таком случае возьмем любую укладку <tex>G_1</tex> на плоскости и переместим точку, соответствующую <tex>v_1</tex> во внешнюю грань. Иначе сожмем часть плоскости, содержащую укладку <tex>G_1</tex> так, чтобы она вмещалась в одну из граней укладки <tex>G_2</tex> смежную с <tex>v_1</tex>. Рассмотрим множество <tex>U</tex> вершин смежных с <tex>v_1</tex>. Уберем кривые, соответствующие ребрам, инцидентным <tex>v_1</tex>. Ясно, что после этого множество вершин <tex>U</tex> лежит на внешней границе укладки <tex>G_1</tex>. Соединим теперь каждую вершину из <tex>U</tex> c <tex>v_2</tex> непересекающимися жордановыми линиями так, чтобы они не задевали укладок <tex>G_1</tex> и <tex>G_2</tex> (рис. 1). Таким образом мы совместили вершины <tex>v_1</tex> и <tex>v_2</tex> в вершине <tex>v_2</tex>, а значит получили укладку графа <tex>G</tex> на сфере, следовательно <tex>G</tex> - планарен.
 +
[[Файл: Planar_vertex_biconnected_1.png|300px|center|thumb|рис. 1.]]
 
}}
 
}}
  
 
Докажем утверждение теоремы для одной из компоненты связности графа <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> - т.с. <tex>G</tex> имеем <tex>deg(v) \ge 2</tex>. Из [[Граф блоков-точек сочленения#lemma1|леммы]] и из связности <tex>T</tex> получаем, что <tex>T</tex> &mdash; двудольное [[Дерево, эквивалентные определения|дерево]].  
+
Итак пусть граф <tex>G</tex> связен. Если <tex>G = K_1</tex>, то <tex>G</tex> очевидно планерен, поэтому предположим, что <tex>|EG| \geqslant 1</tex> , а значит имеется по-крайней мере один блок в <tex>G</tex>. Рассмотрим связный подграф <tex>T</tex> графа блоков и точек сочленений графа <tex>G</tex> такой, что <tex>\forall v</tex> - т.с. <tex>G</tex> имеем <tex>\deg(v) \geqslant 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>).
Строка 30: Строка 31:
 
Пусть утверждение верно для <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> {{---}} т.с. в <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>. Обозначим за <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>.
+
#<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>. Обозначим за <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> (рис. 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>.  
Строка 45: Строка 46:
 
'''Замечание.''' В доказательстве теоремы непосредственно указывается способ получения укладки графа <tex>G</tex> из имеющихся укладок его блоков.
 
'''Замечание.''' В доказательстве теоремы непосредственно указывается способ получения укладки графа <tex>G</tex> из имеющихся укладок его блоков.
  
==Источники==
+
==См. также==
 +
*[[Укладка_графа_с_планарными_компонентами_реберной_двусвязности|Укладка графа с планарными компонентами реберной двусвязности]]
  
Асанов М., Баранский В., Расин В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы {{---}} Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001.
+
==Источники информации==
  
H. Whitney {{---}} Non-separable and planar graphs {{---}} Trans. Amer. Math. Soc., 1932.
+
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
 +
 
 +
* H. Whitney '''Non-separable and planar graphs''' — Trans. Amer. Math. Soc., 1932.
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Укладки графов ]]

Текущая версия на 19:03, 4 сентября 2022

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