Дерево Тремо - Trémaux tree
В теории графов , Trémaux дерево из неориентированного графа G является остовное дерево из G , коренится в одном из своих вершин, с тем свойством , что каждые две соседних вершин в G связаны друг с другом в качестве предка и потомка в дереве. Все деревья поиска в глубину и все гамильтоновы пути являются деревьями Тремо. Деревья Тремо названы в честь Шарля Пьера Тремо, французского писателя XIX века, который использовал поиск в глубину в качестве стратегии для решения лабиринтов . Их также называют нормальными остовными деревьями , особенно в контексте бесконечных графов.
В конечных графах, хотя поиск в глубину сам по себе является последовательным, деревья Тремо могут быть построены с помощью рандомизированного параллельного алгоритма в классе сложности 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- алгоритм для построения деревьев Тремо?
Это P-полное нахождение дерева Тремо, которое может быть найдено с помощью последовательного алгоритма поиска в глубину, в котором соседи каждой вершины ищутся в порядке их идентичности. Тем не менее, можно найти другое дерево Тремо с помощью рандомизированного параллельного алгоритма , показывающего, что конструкция деревьев Тремо принадлежит классу сложности RNC . Алгоритм основан на другом рандомизированном параллельном алгоритме для поиска идеальных совпадений с минимальным весом в 0-1-взвешенных графах. По состоянию на 1997 год оставалось неизвестным, может ли построение дерева Тремо быть выполнено с помощью детерминированного параллельного алгоритма в классе сложности NC . Если сопоставления можно найти в NC, то и деревья Тремо могут быть найдены.
Логическое выражение
Можно выразить свойство, состоящее в том, что множество T ребер с выбором корневой вершины r образует дерево Тремо в монадической логике графов второго порядка , а более конкретно в форме этой логики, называемой MSO 2 , которая позволяет количественная оценка по множеству вершин и ребер. Это свойство может быть выражено как совокупность следующих свойств:
- Графа соединены с помощью ребер в T . Это можно выразить логически как утверждение, что для каждого непустого собственного подмножества вершин графа существует ребро в T с ровно одной конечной точкой в данном подмножестве.
- Т ацикличен. Это может быть выражено логически как утверждение , что не существует непустое подмножество C из T , для которых каждая вершина падает на ноль или два ребра C .
- Каждое ребро е не в Т соединяет предок-потомок пары вершин в T . Это справедливо , когда оба конца е принадлежит к пути в T . Это может быть выражено логически как утверждение , что для всех ребер е , существует подмножество Р из Т таким образом, что ровно две вершины, одна из которых R , инцидентные к одному краю P , и таким образом, что оба конца е являются падающего , по меньшей мере , одного края P .
После того, как дерево Тремо было идентифицировано таким образом, можно описать ориентацию данного графа, также в монадической логике второго порядка, указав набор ребер, ориентация которых находится от предковой конечной точки до конечной конечной точки-потомка. Остальные края за пределами этого набора должны быть ориентированы в другом направлении. Этот метод позволяет задавать свойства графа, включающие ориентации, в монадической логике второго порядка, позволяя эффективно тестировать эти свойства на графах с ограниченной шириной дерева с использованием теоремы Курселя .
Связанные свойства
Если граф имеет гамильтонов путь , то этот путь (с корнем в одной из его конечных точек) также является деревом Тремо. Неориентированные графы, для которых каждое дерево Тремо имеет такую форму, являются графами циклов , полными графами и сбалансированными полными двудольными графами .
Деревья Тремо тесно связаны с концепцией глубины дерева . Древовидность графа G может быть определена как наименьшее число d, такое, что G может быть вложен как подграф графа H, который имеет дерево Тремо T глубины d . Ограниченная глубина дерева в семействе графов эквивалентна существованию пути, который не может быть второстепенным графом графов в семействе. Многие сложные вычислительные задачи на графах имеют алгоритмы, которые можно обрабатывать с фиксированными параметрами, если они параметризованы глубиной дерева входных данных.
Деревья Тремо также играют ключевую роль в критерии планарности Фрейссе – Розенштиля для проверки того, является ли данный граф планарным . Согласно этому критерию граф G является плоским, если для данного дерева Тремо T группы G оставшиеся ребра могут быть последовательно размещены слева или справа от дерева с учетом ограничений, которые не позволяют ребрам с одинаковыми размещение от пересечения друг с другом.
В бесконечных графах
Существование
Не каждый бесконечный граф имеет нормальное остовное дерево. Например, полный граф на несчетном множестве вершин не имеет таковой: нормальное остовное дерево в полном графе может быть только путем, но путь имеет только счетное число вершин. Однако каждый граф на счетном множестве вершин действительно имеет нормальное остовное дерево.
Даже в счетных графах поиск в глубину может не привести в конечном итоге к исследованию всего графа, и не каждое нормальное связующее дерево может быть сгенерировано поиском в глубину: чтобы быть деревом поиска в глубину, счетным нормальным остовным деревом должен иметь только один бесконечный путь или один узел с бесконечным количеством дочерних элементов (но не оба сразу).
Несовершеннолетние
Если бесконечный граф G имеет нормальное связующее дерево, так что делает каждый связный граф минор из G . Отсюда следует, что графы, имеющие нормальные остовные деревья, характеризуются запрещенными минорами . Один из двух классов запрещенных миноров состоит из двудольных графов, в которых одна сторона двудольного деления счетна, другая - несчетна, а каждая вершина имеет бесконечную степень. Другой класс запрещенных миноров состоит из определенных графов, производных от деревьев Ароншайна .
Детали этой характеристики зависят от выбора теоретико-множественной аксиоматизации, используемой для формализации математики. В частности, в моделях теории множеств, для которых верна аксиома Мартина и неверна гипотеза континуума , класс двудольных графов в этой характеристике может быть заменен одним запрещенным минором. Однако для моделей, в которых гипотеза континуума верна, этот класс содержит графы, несравнимые друг с другом в меньшем порядке.
Концы и метризуемость
Нормальные остовные деревья также тесно связаны с концами бесконечного графа, классами эквивалентности бесконечных путей, которые интуитивно уходят в бесконечность в том же направлении. Если граф имеет нормальное остовное дерево, это дерево должно иметь ровно один бесконечный путь для каждого из концов графа.
Бесконечный граф можно использовать для формирования топологического пространства , рассматривая сам граф как симплициальный комплекс и добавляя бесконечно удаленные точки для каждого конца графа. При такой топологии граф имеет нормальное остовное дерево тогда и только тогда, когда его множество вершин можно разложить в счетное объединение замкнутых множеств . Кроме того, это топологическое пространство может быть представлено метрическим пространством тогда и только тогда, когда граф имеет нормальное остовное дерево.