Укладка графа с планарными компонентами рёберной двусвязности — различия между версиями
м (rollbackEdits.php mass rollback) |
|
(не показаны 2 промежуточные версии 2 участников) | |
(нет различий)
|
Текущая версия на 19:18, 4 сентября 2022
Теорема (об укладке графа с планарными компонентами реберной двусвязности): | ||||||||||||
Доказательство: | ||||||||||||
Докажем для начала ряд вспомогательных лемм.
Докажем утверждение теоремы для одной из компонент связности графа леммы и из связности получаем, что — дерево. . Ясно, что имея укладки на плоскости каждой из компонент связности графа, мы можем получить укладку на плоскости и всего графа. Итак пусть граф связен. Рассмотрим связный подграф графа компонент реберной двусвязности графа . ИзДокажем индукцией по числу вершин в графе мостов графа принадлежащих графу планарен (далее будем говорить, что соответствует ). , что подграф графа состоящий из компонент реберной двусвязности иБаза индукции. Если , то граф — тривиальный граф. Его единственная вершина - это компонента реберной двусвязности графа , которая по условию теоремы планарна.Индукционный переход. Пусть утверждение верно для . Рассмотрим , для которого , и соответствующий подграф графа . Докажем, что планарен.Положим мост в инцидентный в (рис. 3). планарен по условию теоремы, т.к. компоненты реберной двусвязности графа совпадают с компонентами реберной двусвязности графа . Далее рассмотрим подграф графа , соответствующий дереву . Поскольку — висячая вершина , то связен, и, очевидно, также как и является подграфом графа компонент реберной двусвязности . Итак планарен по предположению индукции, т.к. . Из определения ребер графа компонент реберной двусвязности получаем, что графы и соединены в графе единственным мостом инцидентным блоку в дереве . Поскольку , то и . Покажем как из укладок и получить укладку . — компонента реберной двусвязности графа являющийся висячей вершиной дерева , a —Уложим лемме II это возможно, рис. 4). Если такого ребра не существует, значит компонента реберной двусвязности — тривиальный граф, в таком случае возьмем любую укладку на плоскости. Пусть — вершина инцидентная . Сожмем часть плоскости, содержащую укладку , так, чтобы она вмещалась в одну из граней укладки смежную с . Проведем жорднанову кривую, соответствующую ребру , от вершины к инцидентной вершине графа так, чтобы она не пересекалась с укладками и . Мы получили укладку графа на сфере, а значит (по лемме I) планарен, следовательно предположение индукции верно. на сфере и уложим на плоскости так, чтобы ребро смежное с в G' (если таковое имеется) оказалось на границе внешней грани (по
| ||||||||||||
Замечание. В доказательстве теоремы непосредственно указывается способ получения укладки графа
из укладок его компонент реберной двусвязности.См. также
Источники информации
- Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
- H. Whitney Non-separable and planar graphs — Trans. Amer. Math. Soc., 1932.