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

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

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

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

Формальное определение

Иллюстрация множеств рёбер $X_{v},Y_{v}$ и $Z_{v}$

Пусть $G_{\phi }$ будет планарным графом. Пусть $T$ будет корневым стягивающим деревом графа $G_{\phi }$. Пусть $P(r,v)=(r=u_{1}),u_{2},\ldots ,(v=u_{k})$ будет путём в $T$ от корня $r$ к вершине $v\neq r$. Путь $P(r,v)$ делит детей $u_{i}$, $(1\leqslant 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$ называется хорошим стягивающим деревом графа $G_{\phi }$, если любая вершина $v$ $(v\neq r)$ графа $G_{\phi }$ удовлетворяет двум условиям по отношению к $P(r,v)$.

• [Условие 1] $G_{\phi }$ не содержит не принадлежащего дереву ребра $(v,u_{i})$, $i<k$
• [Условие 2] рёбра графа $G_{\phi }$, инцидентные вершине $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')\in X_{v}$, $v'$ содержится в $T_{u_{i}^{L}}$ $i<k$, а для каждого ребра $(v,v')\in Z_{v}$, $v'$ содержится в $T_{u_{i}^{R}}$ $i<k$.

    

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

Приложения

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

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

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

См. также

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