53
правки
Изменения
Нет описания правки
<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>
Пусть утверждение верно для <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>e</tex> — мост в <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> — висячая вершина <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> и <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' (если таковое имеется) оказалось на границе внешней грани (по [[#l2|лемме II]] это возможно). Если такого ребра <tex>e_1</tex> не существует, значит к.р.д. <tex>G_1</tex> — тривиальный граф. В таком случае возьмем любую укладку <tex>G_1</tex> на плоскости. Обозначим за Пусть <tex>u</tex> вершину из <tex>\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> планарен, следовательно предположение индукции верно.
</div>
}}
'''Замечание.''' Доказательство теоремы непосредственно задает способ укладки графа <tex>G</tex>из укладок его к.р.д.
==Источники==
Асанов М., Баранский В., Расин В. {{- --}} Дискретная математика: Графы, матроиды, алгоритмы — {{---}} Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001.
H. Whitney {{- --}} Non-separable and planar graphs {{--- }} Trans. Amer. Math. Soc., 1932.
