Цветущие деревья — это деревья с дополнительными ориентированными половинками рёбер. Каждое цветущее дерево ассоциировано с вложением планарного графа. Цветущие деревья могут быть использованы для семплирования случайных планарных графов.
Описание
Цветущее дерево строится из корневого дерева, вложенного в плоскость, путём добавления открытых и замкнутых черешков (половинок рёбер) к вершинам. Число открытых и закрытых черешков должно совпадать. Некоторые авторы требуют, чтобы цветущие деревья были корневыми, и накладывают условия на вид черешков, которые могут приписаны дереву. Для открытых и закрытых черешков иногда используются термины листья и цветы.
Связь с планарными графами
Вложенный планарный граф может быть построен из цветущего дерева путём соединения каждого открытого черешка с замкнутым черешком. Для этого посещают полурёбра вокруг графа по часовой стрелке, начиная с открытого черешка. Если дерево корневое, обычно начинают с корня. Алгоритм аналогичен алгоритму сопоставления скобок и использует стек. На каждой стадии алгоритма если тип текущего полуребра совпадает с типом на вершине стека, помещается в стек. Если цвета отличаются, полуребро из стека выталкивается и два полуребра соединяются. Если мы введём ориентацию рёбер из открытого в замкнутый черешок, мы не получим рёбер против часовой стрелки. Этот процесс занимает линейное время.
Аналогичным образом вложение корневого планарного графа может закодировано как цветущее дерево. Если корень находится в углуПод углом здесь понимается вершина на внешнем периметре графа., это можно сделать за линейное время. Рёбра корневого планарного графа могут быть ориентированы, так что имеется путь из корня в любую вершину, но нет циклов, идущих против часовой стрелки. В этом случае можно использовать алгоритм поиска в глубину для превращения его в цветущее дерево. Начав с корневой вершины, просматривают каждое ребро, инцидентное вершине. Если ребро указывает от текущей вершины, рассекаем его, помечая исходящую половинку как замкнутый черешок, а входящую половинку — как открытый черешок. Если дуга направлена в текущую вершину, помечаем её и противоположную вершину дуги принимаем за текущую вершину. Продолжаем, пока все рёбра не будут просмотрены. Если картаУпотребление слова карта здесь не вполне понятно. Планарная карта – это вложение графа в сферу без пересечения рёбер. Фактически, это то же самое, что и вложение графа в плоскость. имеет корень в углу, построение цветущего дерева занимает квадратичное время .
Использование в теории узлов Цветущие деревья используются также для случайной генерации диаграмм больших узлов. Узлы можно представить как 4-регулярные планарные графы, в которых каждая вершина помечена как пересечение сверху или пересечение снизу. Цветущие деревья могут быть использованы для генерации случайных 4-регулярных планарных графов. Однако это не всегда даёт диаграмму узла, поскольку может содержать более одной компоненты. Это можно проверить за кубическое время.
Примечания
Ссылки
Литература
Категория:Объекты теории графов Категория:Деревья (графы) Категория:Планарные графы