Изменения

|about=Теорема об укладке графа с планарными компонентами вершинной двусвязности.|statement=Если [[Отношение вершинной двусвязности|компоненты вершинной двусвязности]] [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа ]] <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>ev_1</tex> в G' (если таковое имеется) оказалось на границе внешней грани (по [[#l1l2|лемме II]] это возможно). Обозначим за Если такого ребра <tex>e_1</tex> не существует, значит вершина <tex>uv_1</tex> - вершину из изолирована, в таком случае возьмем любую укладку <tex>G_2G_1</tex> инцедентную на плоскости и переместим точку, соответствующую <tex>ev_1</tex>во внешнюю грань. Сожмем Иначе сожмем часть плоскости, содержащую укладку <tex>G_1</tex> так , чтобы она вмещалась в одну из граней укладки <tex>G_2</tex> смежную с <tex>uv_1</tex>. Рассмотрим множество <tex>U</tex> вершин смежных с <tex>u_1v_1</tex>. Отбросим ребра инцидентные Уберем кривые, соответствующие ребрам, инцидентным <tex>u_1v_1</tex>, ясно. Ясно, что после этого мн-во множество вершин <tex>U</tex> - лежат лежит на внешней границе укладки <tex>G_1</tex>. Соединим теперь каждую вершину из <tex>U</tex> c <tex>u_2v_2</tex> не пересекающимися непересекающимися жордановыми линиямитак, так что бы чтобы они не задевали укладок <tex>G_1</tex> и <tex>G_2</tex>(рис. 1). Таким образом мы совместили вершины <tex>u_1v_1</tex> и <tex>u_2v_2</tex> в вершине <tex>u_2v_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 = K_1</tex>, то <tex>G</tex> очевидно планерен, поэтому предположим, что <tex>|EG| \ge 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>).

 <div style="border:1px solid dashed #000; width:90%; margin: 10px; padding:4px; background-color: #fdfdfd; padding-left:10px;">Если <tex>|VT| = 1</tex>, то граф <tex>T</tex> - тривиальный. Его единственная вершина - &mdash; это блок графа <tex>G</tex>, который по утверждению теоремы - планарен.

<div style="border:1px solid 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>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 ) > 01</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\deg(v) = 2</tex> и в <tex>G_2T</tex> соединены в графе (рис. 2). Обозначим за <tex>GT'</tex> единственным мостом <tex>e T\in backslash \{u,v\}</tex>. Поскольку степень ни одной из т.с. <tex>G'</tex> инцидентным блоку принадлежащих <tex>G_1T</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 \{G_1u\}</tex>.[[Файл: Planar vertex biconnected 2.png|270px|center|thumb|рис. 2. Красные {{---}} точки сочленений. Голубые {{---}} блоки.]]#<tex>\cup edeg (v) > 2</tex> в <tex>T</tex> (рис. 3). Обозначим за <tex>T'</tex> <tex>T\cup backslash \{G_2u\}</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>GT'</tex> удовлетворяет условиям на <tex>T</tex> из предположения индукции. Заметим, что <tex>VT' = \{G_1\}\cup e\cup \{G_2\}VT - 1 = m - 1 < m</tex>. Покажем как из укладок Заметим также, что <tex>G_1T'</tex> и связен, т.к. <tex>G_2u</tex> получить укладку была висячей вершиной в <tex>G'T</tex>.[[Файл: Planar vertex biconnected 3.png|270px|center|thumb|рис. 3. Красные {{---}} точки сочленений. Голубые {{---}} блоки.]]

Уложим Рассмотрим подграф <tex>G_2</tex> на сфере и уложим графа <tex>G'</tex> соответствующий дереву <tex>T'</tex>. Поскольку <tex>G_1T'</tex> на плоскости таксвязен, чтобы ребро степени вершин в <tex>e_1 \in G_1T'</tex> смежное соответствующих т.с . графа <tex>eG'</tex> в Gудовлетворяют предположению индукции и, очевидно, также как и <tex>T</tex> граф <tex>T' оказалось на границе внешней грани (по [[#l1|лемме II]] это возможно). Обозначим за </tex> является подграфом графа блоков и точек сочленений <tex>uG</tex> - вершину из , получим, что <tex>G_2</tex> инцедентную планарен по предположению индукции, т.к. <tex>eVT' < m</tex>. Сожмем часть плоскости Из определения ребер дерева блоков и точек сочленений получаем, содержащую укладку что графы <tex>G_1</tex> так чтобы она вмещалась в одну из граней укладки и <tex>G_2</tex> смежную с имеют единственную общую точку {{---}} точку сочленения <tex>uv</tex>. Проводя ребро Поскольку множество блоков <tex>eG'</tex> от вершины принадлежащих <tex>uT</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</tex> и <tex>G_2</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> {{---}} дерево, содержащее хотя бы одно ребро. Поскольку в графе блоков и точек сочленений точки сочленений не могут быть висячими вершинами, то каждая из т.с. графа <tex>G</tex> получаем принадлежащих <tex>T_G</tex> имеет степень как минимум <tex>2</tex>. Получаем, что <tex>T_G</tex> удовлетворяет условиям на <tex>T</tex> из предположения индукции, а значит <tex>G</tex> - планарен.

'''Замечание.''' В доказательстве теоремы непосредственно указывается способ получения укладки графа <tex>G</tex> из имеющихся укладок его блоков. ==См. также==*[[Укладка_графа_с_планарными_компонентами_реберной_двусвязности|Укладка графа с планарными компонентами реберной двусвязности]] ==Источникиинформации== * Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5

Асанов М* H., Баранский ВWhitney '''Non-separable and planar graphs''' — Trans. Amer. Math., Расин ВSoc. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 20011932.