Дерево Тремо - Trémaux tree

В теория графов, а Дерево Тремо из неориентированный граф грамм это остовное дерево из грамм, с корнем в одной из его вершин, с тем свойством, что каждые две смежные вершины в грамм связаны друг с другом как предок и потомок в дереве. Все деревья поиска в глубину и все Гамильтоновы пути деревья Тремо названы в честь Шарля Пьера Тремо, французского писателя XIX века, который использовал поиск в глубину как стратегию поиска. решение лабиринтов.[1][2] Их также называли нормальные остовные деревья, особенно в контексте бесконечных графов.[3]

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

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

Пример

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

Ненаправленный graph.svg

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

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

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

Каждый конечный связаны неориентированный граф имеет хотя бы одно дерево Тремо. Такое дерево можно построить, выполнив поиск в глубину и соединение каждой вершины (кроме начальной вершины поиска) с более ранней вершиной, из которой она была обнаружена. Построенное таким образом дерево известно как дерево поиска в глубину. Если УФ - произвольное ребро в графе, а ты - это более ранняя из двух вершин, которые должны быть достигнуты при поиске, то v должен принадлежать к поддереву, происходящему от ты в дереве поиска в глубину, потому что поиск обязательно обнаружит v пока он исследует это поддерево, либо из одной из других вершин в поддереве, либо, в противном случае, из ты напрямую. Каждое конечное дерево Тремо можно сгенерировать как дерево поиска в глубину: если Т является деревом Тремо конечного графа, а поиск в глубину исследует детей в Т каждой вершины до исследования любых других вершин, она обязательно сгенерирует Т как его дерево поиска в глубину.

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

Вопрос, Web Fundamentals.svgНерешенная проблема в информатике:
Есть детерминированная параллель NC алгоритм построения деревьев Тремо?
(больше нерешенных проблем в информатике)

это P-полный найти дерево Тремо, которое может быть найдено с помощью алгоритма последовательного поиска в глубину, в котором соседи каждой вершины ищутся в порядке их идентичности.[4] Тем не менее, можно найти другое дерево Тремо случайным образом. параллельный алгоритм, показывающий, что конструкция деревьев Тремо принадлежит классу сложности RNC.[5] По состоянию на 1997 год оставалось неизвестным, может ли построение дерева Тремо быть выполнено с помощью детерминированного параллельного алгоритма в классе сложности NC.[6]

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

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

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

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

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

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

Деревья Тремо тесно связаны с концепцией глубина дерева. Древовидная глубина графа грамм можно определить как наименьшее число d такой, что грамм может быть вложен как подграф графа ЧАС с деревом Тремо Т глубины d. Ограниченная глубина дерева в семействе графов эквивалентна существованию пути, который не может быть граф минор графов в семье. Многие сложные вычислительные задачи на графах имеют алгоритмы, которые управляемый с фиксированными параметрами когда параметризованы глубиной дерева их входных данных.[9]

Деревья Тремо также играют ключевую роль в Критерий планарности Фрейссе – Розенштейля для проверки того, является ли данный граф планарный. По этому критерию график грамм является плоским, если для данного дерева Тремо Т из граммоставшиеся ребра могут быть размещены последовательно слева или справа от дерева с учетом ограничений, которые не позволяют ребрам с одинаковым размещением пересекать друг друга.[10]

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

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

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

Даже в счетных графах поиск в глубину может не дать в конечном итоге исследования всего графа,[3] и не каждое нормальное связующее дерево может быть сгенерировано поиском в глубину: чтобы быть деревом поиска в глубину, счетное нормальное остовное дерево должно иметь только один бесконечный путь или один узел с бесконечным числом дочерних элементов (а не оба сразу).

Несовершеннолетние

Если бесконечный граф грамм имеет нормальное остовное дерево, как и все подключенные граф минор из грамм. Из этого следует, что графы, имеющие нормальные остовные деревья, имеют характеристику запрещенный несовершеннолетние. Один из двух классов запрещенных несовершеннолетних состоит из двудольные графы в котором одна сторона двудольного деления счетна, другая - несчетна, и каждая вершина имеет бесконечную степень. Другой класс запрещенных миноров состоит из определенных графов, производных от Деревья Ароншайн.[11]

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

Концы и метризуемость

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

Бесконечный граф можно использовать для формирования топологическое пространство рассматривая сам график как симплициальный комплекс и добавив точка в бесконечности для каждого конца графика. При такой топологии граф имеет нормальное остовное дерево тогда и только тогда, когда его множество вершин может быть разложено в счетное объединение закрытые наборы. Кроме того, это топологическое пространство может быть представлено метрическое пространство тогда и только тогда, когда граф имеет нормальное остовное дерево.[13]

Рекомендации

  1. ^ Эвен, Шимон (2011), Графические алгоритмы (2-е изд.), Cambridge University Press, стр. 46–48, ISBN  978-0-521-73653-4.
  2. ^ Седжвик, Роберт (2002), Алгоритмы в C ++: алгоритмы графов (3-е изд.), Pearson Education, стр. 149–157, ISBN  978-0-201-36118-6.
  3. ^ а б c Соукуп, Лайош (2008), «Бесконечная комбинаторика: от конечного к бесконечному», Горизонты комбинаторики, Bolyai Soc. Математика. Stud., 17, Берлин: Springer, стр. 189–213, Дои:10.1007/978-3-540-77200-2_10, ISBN  978-3-540-77199-9, МИСТЕР  2432534. См., В частности, теорему 3, п. 193.
  4. ^ Рейф, Джон Х. (1985), «Поиск в глубину по своей сути является последовательным», Письма об обработке информации, 20 (5): 229–234, Дои:10.1016/0020-0190(85)90024-9, МИСТЕР  0801987.
  5. ^ Aggarwal, A .; Андерсон, Р. Дж. (1988), «Случайный NC алгоритм поиска в глубину », Комбинаторика, 8 (1): 1–12, Дои:10.1007 / BF02122548, МИСТЕР  0951989.
  6. ^ Каргер, Дэвид Р.; Мотвани, Раджив (1997), "An NC алгоритм минимальных разрезов », SIAM Журнал по вычислениям, 26 (1): 255–272, Дои:10.1137 / S0097539794273083, МИСТЕР  1431256.
  7. ^ Курсель, Бруно (1996), «О выражении свойств графа в некоторых фрагментах монадической логики второго порядка» (PDF), в Иммерман, Нил; Колайтис, Фокион Г. (ред.), Proc. Descr. Сложный. Конечные модели, DIMACS, 31, Амер. Математика. Soc., Стр. 33–62, МИСТЕР  1451381.
  8. ^ Чартран, Гэри; Кронк, Хадсон В. (1968), "Случайно прослеживаемые графы", Журнал SIAM по прикладной математике, 16 (4): 696–700, Дои:10.1137/0116056, МИСТЕР  0234852.
  9. ^ Нешетржил, Ярослав; Оссона де Мендес, Патрис (2012), «Глава 6. Деревья с ограниченной высотой и глубиной дерева», Разреженность: графики, структуры и алгоритмы, Алгоритмы и комбинаторика, 28, Heidelberg: Springer, стр. 115–144, Дои:10.1007/978-3-642-27875-4, ISBN  978-3-642-27874-7, МИСТЕР  2920058.
  10. ^ де Фрейссе, Юбер; Розенштиль, Пьер (1982), "Характеристика планарности методом поиска в глубину", Теория графов (Кембридж, 1981), Анна. Дискретная математика., 13, Амстердам: Северная Голландия, стр. 75–80, МИСТЕР  0671906; де Фрейссе, Юбер; Оссона де Мендес, Патрис; Розенштиль, Пьер (2006), «Деревья Тремо и планарность», Международный журнал основ информатики, 17 (5): 1017–1029, arXiv:математика / 0610935, Дои:10.1142 / S0129054106004248, МИСТЕР  2270949.
  11. ^ Дистель, Рейнхард; Лидер, Имре (2001), «Обычные остовные деревья, деревья Ароншайн и исключенные несовершеннолетние» (PDF), Журнал Лондонского математического общества, Вторая серия, 63 (1): 16–32, Дои:10.1112 / S0024610700001708, МИСТЕР  1801714.
  12. ^ Боулер, Натан; Гешке, Стефан; Питц, Макс (2016), Минимальные препятствия для нормальных остовных деревьев, arXiv:1609.01042, Bibcode:2016arXiv160901042B
  13. ^ а б Дистель, Рейнхард (2006), «Конечные пространства и остовные деревья», Журнал комбинаторной теории, Серия B, 96 (6): 846–854, Дои:10.1016 / j.jctb.2006.02.010, МИСТЕР  2274079.