Дерево Тремо неориентированного графа G — это остовное дерево графа G с выделенным корнем со свойством, что любые две смежные вершины в графе G связаны друг с другом отношением предок/потомок. Все деревья поиска в глубину и все гамильтоновы пути являются деревьями Тремо. Деревья Тремо названы именем Шарля Пьера Тремо, французского автора 19-го века, который использовал вариант поиска в глубину как стратегию . Деревья Тремо также называют нормальными остовными деревьями , особенно в контексте бесконечных графов .

В конечных графах, хотя поиск в глубину сам по себе изначально последователен, деревья Тремо могут быть построены рандомизированным параллельным алгоритмом с классом сложности RNC . Деревья Тремо можно использовать для определения глубины дерева графа и как часть для проверки, является ли граф планарным . Описание деревьев Тремо одноместной второго порядка позволяет распознать эффективно свойства графа, зависимые от ориентации , для графов с ограниченной древесной шириной при использовании теоремы Курселя .

Не любой бесконечный граф имеет дерево Тремо и графы, такого дерева не имеющие, можно описать запрещёнными минорами . Дерево Тремо существует в любом графе со счётным числом вершин, даже если вариант бесконечного поиска в глубину не может успешно проверить все вершины графа. В бесконечном графе дерево Тремо должно иметь в точности один бесконечный путь для каждого графа и существование дерева Тремо характеризует графы, топологические пополнения которых, образованные добавлением бесконечно удалённой точки для каждого луча, являются метрическими пространствами .

Пример

В графе, показанном ниже, дерево с рёбрами 1–3, 2–3 и 3–4 является деревом Тремо, если его корнем назначить вершину 1 или вершину 2 — любое ребро графа принадлежит дереву, за исключением ребра 1–2, которое (при выборе указанного корне) соединяет пару предок-потомок.

Однако, если выбрать в качестве корня для того же дерева вершину 3 или вершину 4, получим корневое дерево, не являющееся деревом Тремо, поскольку с этими корнями вершины 1 и 2 уже не будут предком/потомком.

В конечных графах

Существование

Любой конечный связный неориентированный граф имеет по меньшей мере одно дерево Тремо. Можно построить такое дерево с помощью поиска в глубину и соединения каждой вершины (отличной от начальной вершины поиска) с более ранней вершиной, из которой был получен доступ к текущей вершине. Дерево, построенное таким образом, известно как дерево поиска в глубину. Если uv является произвольным ребром в графе и u является более ранней из двух вершин, достигнутых в результате поиска, тогда v должна принадлежать поддереву потомков u в дереве поиска в глубину, поскольку поиск необходимым образом обнаружит вершину v , просматривая это дерево либо из одного из вершин поддерева, либо непосредственно из вершины u . Любое конечное дерево Тремо может быть образовано как дерево поиска в глубину — если T является деревом Тремо конечного графа и поиск в глубину исследует потомков T каждой вершины перед рассмотрением любой другой вершины, это необходимым образом генерирует T как дерево поиска в глубину графа.

Параллельное построение

: Существует ли детерминированный параллельный алгоритм класса NC для построения деревьев Тремо?

Задача поиска дерева Тремо является , если ищется с помощью последовательного алгоритма поиска в глубину, в котором соседи каждой вершины просматриваются в порядке их номеров . Тем не менее, можно найти другое дерево Тремо при использовании рандомизированного параллельного алгоритма , что показывает принадлежность построения деревьев Тремо классу сложности RNC . Остаётся неизвестным, может ли дерево Тремо быть построено детерминированным параллельным алгоритмом, принадлежащим классу NC .

Логическое выражение

Можно выразить свойство, что множество T рёбер с выбранной корневой вершиной r образует дерево Тремо, в одноместной второго порядка, и такое выражение называется MSO ₂ . Это свойство можно выразить как сочетание следующих свойств:

• Граф связан рёбрами из T . Это можно выразить логически как утверждение, что для любого непустого собственного подмножества вершин графа существует ребро в T , имеющее в точности одну конечную точку в этом подмножестве.
• T ациклично. Это можно выразить логически как утверждение, что не существует непустого подмножества C множества T , для которого каждая вершина инцидентна либо нулю, либо двум рёбрам из C .
• Любое ребро e , не принадлежащее T , соединяет пару предок/потомок вершин в T . Это верно, когда оба конца ребра e принадлежат пути в T . Это можно выразить логически как утверждение, что для всех рёбер e существует подмножества P множества T , такое, что в точности две вершины, одна из которых r , инцидентны одному ребру в P , и оба конца дуги e инцидентны по меньшей мере одному ребру в P .

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

Связанные свойства

Если граф имеет гамильтонов путь , то этот путь (с корнем в качестве одного из его концов) является также деревом Тремо. Множество неориентированных графов, для которых любое дерево Тремо имеет такой вид, состоит из циклов , полных графов и сбалансированных полных двудольных графов .

Деревья Тремо тесно связаны с концепцией глубины дерева . Глубина дерева графа G может быть определена как наименьшее число d , такое, что G может быть вложено в виде подграфа графа H , который имеет дерево Тремо T глубины d . Ограниченная глубина дерева в семействе графов эквивалентна существованию пути, который не может появиться в качестве минора графа в семействе. Много сложных вычислительных задач на графах имеют алгоритмы, если параметризовать глубиной дерева .

Деревья Тремо играют также ключевую роль в для проверки, является ли граф планарным . Согласно этому критерию граф G планарен, если для любого дерева Тремо T графа G оставшиеся рёбра можно расположить слева и справа от дерева, что предотвращает пересечение рёбер (по этой причине иногда можно видеть название «ЛП алгоритм» — аббревиатура Левый/Правый) .

В бесконечных графах

Существование

Не любой бесконечный граф имеет нормальное остовное дерево. Например, полный граф на несчётном множестве вершин не имеет нормального остовного дерева — такое дерево в полном графе может быть только путём, но путь имеет лишь счётное число вершин. Однако любой граф на счётном множестве вершин имеет нормальное остовное дерево .

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

Миноры

Если бесконечный граф G имеет нормальное остовное дерево, то такой имеет и любой связный минор графа G . Отсюда следует, что графы, имеющие нормальные остовные остовные деревья, можно описать запрещёнными минорами . Один из двух классов запрещённых миноров состоит из двудольных графов , в которых одна доля счётна, а другая несчётна, и любая вершина имеет бесконечную степень. Другой класс запрещённых миноров состоит из определённых графов, полученных из .

Детали этого описания зависят от выбора аксиоматики теории множеств, используемой в формализации математики. В частности, в моделях теории множеств, в которых верна аксиома Мартина , а континуум-гипотеза не верна, класс двудольных графов может быть заменён одним запрещённым минором. Однако для моделей, в которых континуум-гипотеза верна, этот класс содержит графы, которые несравнимы в упорядочении миноров .

Лучи и метризуемость

Нормальные остовные деревья тесно связаны с бесконечного графа, классами эквивалентности бесконечных путей, которые идут в одном и том же направлении. Если граф имеет нормальное остовное дерево, это дерево должно иметь в точности один бесконечный путь для каждого луча графа .

Бесконечный граф можно использовать для образования топологического пространства , если рассматривать граф сам по себе как симплициальный комплекс и добавить бесконечно удалённую точку для каждого луча графа. С такой топологией граф имеет нормальное остовное дерево тогда и только тогда, когда его множество вершин можно разбить на счётное объединение замкнутых множеств . Кроме того, это топологическое пространство может быть представлено метрическим пространством тогда и только тогда, когда граф имеет нормальное остовное дерево .

Примечания

Литература