Цветущее дерево (теория графов)

Цветущие деревья — это деревья с дополнительными ориентированными половинками рёбер. Каждое цветущее дерево ассоциировано с вложением планарного графа. Цветущие деревья могут быть использованы для семплирования случайных планарных графов.

Описание

Цветущее дерево (открытые черешки показаны красным, замкнутые черешки показаны синим)

Цветущее дерево строится из корневого дерева, вложенного в плоскость, путём добавления открытых и замкнутых черешков (половинок рёбер) к вершинам. Число открытых и закрытых черешков должно совпадать. Некоторые авторы требуют, чтобы цветущие деревья были корневыми, и накладывают условия на вид черешков, которые могут приписаны дереву. Для открытых и закрытых черешков иногда используются термины листья и цветы.

Связь с планарными графами

Планарный граф, полученный из цветущего дерева выше. Зелёные линии соединяют открытые и замкнутые черешки.

Вложенный планарный граф может быть построен из цветущего дерева путём соединения каждого открытого черешка с замкнутым черешком. Для этого посещают полурёбра вокруг графа по часовой стрелке, начиная с открытого черешка. Если дерево корневое, обычно начинают с корня. Алгоритм аналогичен алгоритму сопоставления скобок и использует стек. На каждой стадии алгоритма если тип текущего полуребра $s$ совпадает с типом на вершине стека, $s$ помещается в стек. Если цвета отличаются, полуребро из стека выталкивается и два полуребра соединяются. Если мы введём ориентацию рёбер из открытого в замкнутый черешок, мы не получим рёбер против часовой стрелки. Этот процесс занимает линейное время.

Аналогичным образом вложение корневого планарного графа может закодировано как цветущее дерево. Если корень находится в углу, это можно сделать за линейное время. Рёбра корневого планарного графа могут быть ориентированы, так что имеется путь из корня в любую вершину, но нет циклов, идущих против часовой стрелки. В этом случае можно использовать алгоритм поиска в глубину для превращения его в цветущее дерево. Начав с корневой вершины, просматривают каждое ребро, инцидентное вершине. Если ребро указывает от текущей вершины, рассекаем его, помечая исходящую половинку как замкнутый черешок, а входящую половинку — как открытый черешок. Если дуга направлена в текущую вершину, помечаем её и противоположную вершину дуги принимаем за текущую вершину. Продолжаем, пока все рёбра не будут просмотрены. Если карта имеет корень в углу, построение цветущего дерева занимает квадратичное время .

Использование в теории узлов

Цветущие деревья используются также для случайной генерации диаграмм больших узлов. Узлы можно представить как 4-регулярные планарные графы, в которых каждая вершина помечена как пересечение сверху или пересечение снизу. Цветущие деревья могут быть использованы для генерации случайных 4-регулярных планарных графов. Однако это не всегда даёт диаграмму узла, поскольку может содержать более одной компоненты. Это можно проверить за кубическое время.