Цветущие деревья — это деревья с дополнительными ориентированными половинками рёбер. Каждое цветущее дерево ассоциировано с вложением планарного графа. Цветущие деревья могут быть использованы для семплирования случайных планарных графовШаблон:R.
Цветущее дерево строится из корневого дерева, вложенного в плоскость, путём добавления открытых и замкнутых черешков (половинок рёбер) к вершинам. Число открытых и закрытых черешков должно совпадатьШаблон:R. Некоторые авторы требуют, чтобы цветущие деревья были корневыми, и накладывают условия на вид черешков, которые могут приписаны деревуШаблон:Sfn. Для открытых и закрытых черешков иногда используются термины листья и цветыШаблон:SfnШаблон:R.
Связь с планарными графами
Файл:Completed blossom tree.pngПланарный граф, полученный из цветущего дерева выше. Зелёные линии соединяют открытые и замкнутые черешки.
Вложенный планарный граф может быть построен из цветущего дерева путём соединения каждого открытого черешка с замкнутым черешком. Для этого посещают полурёбра вокруг графа по часовой стрелке, начиная с открытого черешка. Если дерево корневое, обычно начинают с корня. Алгоритм аналогичен алгоритму сопоставления скобок и использует стек. На каждой стадии алгоритма если тип текущего полуребра <math>s</math> совпадает с типом на вершине стека, <math>s</math> помещается в стек. Если цвета отличаются, полуребро из стека выталкивается и два полуребра соединяютсяШаблон:R. Если мы введём ориентацию рёбер из открытого в замкнутый черешок, мы не получим рёбер против часовой стрелки. Этот процесс занимает линейное времяШаблон:R.
Аналогичным образом вложение корневого планарного графа может закодировано как цветущее дерево. Если корень находится в углу[примечание 1]Шаблон:R, это можно сделать за линейное время. Рёбра корневого планарного графа могут быть ориентированы, так что имеется путь из корня в любую вершину, но нет циклов, идущих против часовой стрелки. В этом случае можно использовать алгоритм поиска в глубину для превращения его в цветущее дерево. Начав с корневой вершины, просматривают каждое ребро, инцидентное вершине. Если ребро указывает от текущей вершины, рассекаем его, помечая исходящую половинку как замкнутый черешок, а входящую половинку — как открытый черешок. Если дуга направлена в текущую вершину, помечаем её и противоположную вершину дуги принимаем за текущую вершину. Продолжаем, пока все рёбра не будут просмотрены. Если карта[примечание 2] имеет корень в углу, построение цветущего дерева занимает квадратичное время Шаблон:R.
Использование в теории узлов
Цветущие деревья используются также для случайной генерации диаграмм больших узлов. Узлы можно представить как 4-регулярные планарные графы, в которых каждая вершина помечена как пересечение сверху или пересечение снизу. Цветущие деревья могут быть использованы для генерации случайных 4-регулярных планарных графов. Однако это не всегда даёт диаграмму узла, поскольку может содержать более одной компоненты. Это можно проверить за кубическое времяШаблон:Sfn.
Примечания
↑Под углом здесь понимается вершина на внешнем периметре графа.
↑Употребление слова карта здесь не вполне понятно. Планарная карта – это вложение графа в сферу без пересечения рёбер. Фактически, это то же самое, что и вложение графа в плоскость.
