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

В математической области теории графов хорошее остовное дерево [1] встроенного планарного графа корневое связующее дерево представляет собой чьи недревесные ребра удовлетворяют следующим условиям.
- нет ребра, не являющегося деревом где и лежать на пути от корня к листу,
- ребра, инцидентные вершине можно разделить на три комплекта и , где,
- представляет собой набор недревесных ребер, они заканчиваются в красной зоне
- представляет собой набор ребер дерева, они являются детьми
- представляет собой набор недревесных ребер, оканчивающихся зеленой зоной
Формальное определение
[ редактировать ]
Позволять быть плоским графом. Позволять быть корневым связующим деревом . Позволять быть путем в от корня в вершину . Путь разделяет детей , , кроме , на две группы; левая группа и правильная группа . Ребенок из находится в группе и обозначается если край появляется перед краем в порядке часовой стрелки ребер, инцидентных когда заказ начинается с края . Аналогично, ребенок из есть в группе и обозначается если край появляется после края по часовой стрелке от ребер, инцидентных когда заказ начинается с края . Дерево называется хорошим связующим деревом [1] из если каждая вершина из удовлетворяет следующим двум условиям относительно .
- [Условие1] не имеет ребра, не являющегося деревом , ; и
- [Cond2] края инцидентный вершине исключая можно разделить на три непересекающихся (возможно, пустых) множества. и удовлетворяющие следующим условиям (a)-(c)
- (а) Каждый из и представляет собой набор последовательных недревесных ребер и представляет собой набор последовательных ребер дерева.
- (б) Края множества , и появляются по часовой стрелке в этом порядке от края .
- (c) Для каждого ребра , содержится в , , и для каждого ребра , содержится в , .
Плоский граф (вверху), хорошее связующее дерево из (внизу) сплошные ребра являются частью хорошего остовного дерева, а пунктирные ребра - это ребра, не являющиеся деревьями в относительно .
Приложения
[ редактировать ]При монотонном рисовании графиков [2] в 2-видимом представлении графов. [1]
Поиск хорошего связующего дерева
[ редактировать ]Каждый планарный граф имеет вложение такой, что содержит хорошее связующее дерево. Хорошее остовное дерево и подходящее вложение можно найти из в линейном времени. [1] Не все вложения содержать хорошее связующее дерево.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б с д и Хоссейн, штат Мэриленд Икбал; Рахман, Мэриленд Саидур (23 ноября 2015 г.). «Хорошие связующие деревья в рисовании графов» . Теоретическая информатика . 607 : 149–165. дои : 10.1016/j.tcs.2015.09.004 .
- ^ Jump up to: а б Хоссейн, штат Мэриленд Икбал; Рахман, доктор Саидур (28 июня 2014 г.). «Монотонные сеточные рисунки плоских графов». Границы в алгоритмике . Конспекты лекций по информатике. Том. 8497. Спрингер, Чам. стр. 105–116. arXiv : 1310.6084 . дои : 10.1007/978-3-319-08016-1_10 . ISBN 978-3-319-08015-4 . S2CID 10852618 .