53
правки
Изменения
Новая страница: «{{Теорема |about=Теорема об укладке графа с планарными компонентами вершинной двусвязности. |…»
{{Теорема
|about=Теорема об укладке графа с планарными компонентами вершинной двусвязности.
|statement=Если [[Отношение вершинной двусвязности|компоненты вершинной двусвязности]] графа <tex>G</tex> планарны, то и сам граф <tex>G</tex> планарен.
|proof=
Докажем вспомогательную лемму.
{{Лемма
|id=l1
|about=I
|statement=Пусть графы <tex>G_1</tex> и <tex>G_2</tex> планарны. Граф <tex>G</tex> получается из <tex>G_1</tex> и <tex>G_2</tex> совмещением вершин <tex>v_1 \in G_1</tex> и <tex>v_2 \in G_2</tex>. Тогда <tex>G</tex> планарен.
|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</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>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;">
Если <tex>|VT| = 1</tex>, то граф <tex>T</tex> - тривиальный. Его единственная вершина - это блок графа <tex>G</tex>, который по утверждению теоремы - планарен.
</div>
'''Индукционный переход.'''
<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>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>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> - для нее степень уменьшилась ровно на 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_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> планарен, следовательно предположение индукции верно.
</div>
Рассматривая в качестве <tex>T</tex> граф компонент реберной двусвязности <tex>G</tex> получаем что <tex>G</tex> - планарен.
}}
==Источники==
Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001.
H. Whitney - Non-separable and planar graphs - Trans. Amer. Math. Soc., 1932.
|about=Теорема об укладке графа с планарными компонентами вершинной двусвязности.
|statement=Если [[Отношение вершинной двусвязности|компоненты вершинной двусвязности]] графа <tex>G</tex> планарны, то и сам граф <tex>G</tex> планарен.
|proof=
Докажем вспомогательную лемму.
{{Лемма
|id=l1
|about=I
|statement=Пусть графы <tex>G_1</tex> и <tex>G_2</tex> планарны. Граф <tex>G</tex> получается из <tex>G_1</tex> и <tex>G_2</tex> совмещением вершин <tex>v_1 \in G_1</tex> и <tex>v_2 \in G_2</tex>. Тогда <tex>G</tex> планарен.
|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</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>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;">
Если <tex>|VT| = 1</tex>, то граф <tex>T</tex> - тривиальный. Его единственная вершина - это блок графа <tex>G</tex>, который по утверждению теоремы - планарен.
</div>
'''Индукционный переход.'''
<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>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>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> - для нее степень уменьшилась ровно на 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_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> планарен, следовательно предположение индукции верно.
</div>
Рассматривая в качестве <tex>T</tex> граф компонент реберной двусвязности <tex>G</tex> получаем что <tex>G</tex> - планарен.
}}
==Источники==
Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001.
H. Whitney - Non-separable and planar graphs - Trans. Amer. Math. Soc., 1932.
