Хорошее стягивающее дерево

Условия хорошего стягивающего дерева

Хорошее стягивающее деревоШаблон:Sfn $T$ вложенного планарного графа $G$ — это корневое остовное дерево графа $G$, не принадлежащие дереву рёбра которого удовлетворяют следующим условиям:

• нет не принадлежащего дереву ребра $(u,v)$, в котором вершины $u$ и $v$ лежат на пути из корня дерева $T$ в лист,
• рёбра, инцидентные вершине $v$, могут быть разбиты на три множества $X_v,Y_v$ и $Z_v$, где
  • $X_v$ является множеством не принадлежащих дереву рёбер, они определяют красную зону
  • $Y_v$ является множеством рёбер дерева, они являются детьми вершины $v$
  • $Z_v$ является множеством не принадлежащих дереву рёбер, они определяют зелёную зону

Формальное определениеШаблон:SfnШаблон:Sfn

Иллюстрация множеств рёбер $X_v,Y_v$ и $Z_v$

Пусть $G_{\varphi }$ будет планарным графом. Пусть $T$ будет корневым стягивающим деревом графа $G_{\varphi }$. Пусть $P(r,v)=(r=u_1),u_2,\dots ,(v=u_k)$ будет путём в $T$ от корня $r$ к вершине $v\ne r$. Путь $P(r,v)$ делит детей $u_i$, $(1⩽i<k)$, за исключением $u_{i+1}$, на две группы. Левую группу $L$ и правую группу $R$. Дочерняя вершина $x$ вершины $u_i$ находится в группе $L$ и обозначается как $u_i^L$, если ребро $(u_i,x)$ появляется до ребра $(u_i,u_{i+1})$ при упорядочении по часовой стрелке рёбер, инцидентных $u_i$, если упорядочение начинается с $(u_i,u_{i+1})$. Аналогично, дочерняя вершина $x$ вершины $u_i$ находится в группе $R$ и обозначается как $u_i^R$, если ребро $(u_i,x)$ появляется после ребра $(u_i,u_{i+1})$ в упорядочении по часовой стрелке рёбер, инцидентных $u_i$, если упорядочение начинается с ребра $(u_i,u_{i+1})$. Дерево $T$ называется хорошим стягивающим деревомШаблон:Sfn графа $G_{\varphi }$, если любая вершина $v$ $(v\ne r)$ графа $G_{\varphi }$ удовлетворяет двум условиям по отношению к $P(r,v)$.

• [Условие 1] $G_{\varphi }$ не содержит не принадлежащего дереву ребра $(v,u_i)$, $i<k$
• [Условие 2] рёбра графа $G_{\varphi }$, инцидентные вершине $v$, исключая $(u_{k-1},v)$, могут быть разбиты на три непересекающиеся (возможно пустых) множества $X_v,Y_v$ и $Z_v$, удовлетворяющих условиям (a)-(c)
  • (a) Каждое из множеств $X_v$ и $Z_v$ является множеством не принадлежащих дереву рёбер, а $Y_v$ является множеством рёбер дерева.
  • (b) Рёбра множеств $X_v$, $Y_v$ и $Z_v$ появляются по часовой стрелке в этом порядке от ребра $(u_{k-1},v)$.
  • (c) Для каждого ребра $(v,v^{\prime })\in X_v$, $v^{\prime }$ содержится в $T_{u_i^L}$ $i<k$, а для каждого ребра $(v,v^{\prime })\in Z_v$, $v^{\prime }$ содержится в $T_{u_i^R}$ $i<k$.

    

    Планарный граф $G_{\varphi }$ (сверху), хорошее стягивающее дерево $T$ графа $G_{\varphi }$ (внизу), сплошные рёбра являются частями хорошего стягивающего дерева, а пунктирные рёбра не принадлежат дереву $T$.

Приложения

Применяется в мнототонном рисовании графовШаблон:Sfn и в прямоугольном представлении графовШаблон:Sfn.

Поиск хорошего стягивающего дерева

Любой планарный граф $G$ имеет вложение $G_{\varphi }$, такое, что $G_{\varphi }$ содержит хорошее стягивающее дерево. Хорошее стягивающее дерево и подходящее вложение могут быть найдены для графа $G$ за линейное времяШаблон:Sfn. Не все вложения графа $G$ содержат хорошее стягивающее дерево.

См. также

• Остовное дерево
• Реализатор Шнайдера

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга