Хорошее связующее дерево

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

В математической области теории графов хорошее остовное дерево $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\leq 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$; и
• [Cond2] края $G_{\phi }$ инцидентный вершине $v$ исключая $(u_{k-1},v)$ можно разделить на три непересекающихся (возможно, пустых) множества. $X_{v},Y_{v}$ и $Z_{v}$ удовлетворяющие следующим условиям (a)-(c)
  • (а) Каждый из $X_{v}$ и $Z_{v}$ представляет собой набор последовательных недревесных ребер и $Y_{v}$ представляет собой набор последовательных ребер дерева.
  • (б) Края множества $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 }$ (внизу) сплошные ребра являются частью хорошего остовного дерева, а пунктирные ребра - это ребра, не являющиеся деревьями в $G_{\phi }$ относительно $T$.

Приложения

При монотонном рисовании графиков в 2-видимом представлении графов.

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

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

См. также

• Связующее дерево
• реализатор Шнайдера