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

Теорема (об укладке графа с планарными компонентами вершинной двусвязности):

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

H. Whitney — Non-separable and planar graphs — Trans. Amer. Math. Soc., 1932.