Дерево Тремо

Обобщение деревьев поиска в глубину

В теории графов дерево Тремо неориентированного графа — это тип остовного дерева , обобщающий деревья поиска в глубину . Они определяются свойством, что каждое ребро соединяет пару предок-потомок в дереве. Деревья Тремо названы в честь Шарля Пьера Тремо, французского автора 19 века, который использовал форму поиска в глубину в качестве стратегии для решения лабиринтов . ^{[1] [2]} Их также называют нормальными остовными деревьями , особенно в контексте бесконечных графов. ^{[3] [4]} ${\displaystyle G}$ ${\displaystyle G}$

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

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

Определение и примеры

Дерево Тремо для графа — это остовное дерево со свойством, что для каждого ребра в одна из двух конечных точек и является предком другого. Чтобы быть остовным деревом, оно должно использовать только ребра из и включать каждую вершину с уникальным конечным путем между каждой парой вершин. Кроме того, для определения отношения предок-потомок в этом дереве одна из его вершин должна быть обозначена как его корень. ${\displaystyle G}$ ${\displaystyle T}$ ${\displaystyle uv}$ ${\displaystyle G}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G}$

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

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

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

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

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

Каждый конечный связный неориентированный граф имеет по крайней мере одно дерево Тремо. ^[4] Такое дерево можно построить, выполнив поиск в глубину и соединив каждую вершину (кроме начальной вершины поиска) с более ранней вершиной, из которой она была обнаружена. Дерево, построенное таким образом, известно как дерево поиска в глубину. Если — произвольное ребро в графе, и — более ранняя из двух вершин, до которых должен быть достигнут поиск, то должно принадлежать поддереву, спускающемуся с в дереве поиска в глубину, потому что поиск обязательно обнаружит во время исследования этого поддерева либо из одной из других вершин в поддереве, либо, в противном случае, непосредственно из. Каждое конечное дерево Тремо может быть сгенерировано как дерево поиска в глубину: Если — дерево Тремо конечного графа, и поиск в глубину исследует дочерние вершины в каждой вершине до исследования любых других вершин, он обязательно сгенерирует как свое дерево поиска в глубину. ${\displaystyle uv}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle T}$

Параллельная конструкция

Нерешенная проблема в информатике :

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

(еще нерешенные проблемы в информатике)

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

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

Можно выразить свойство, что набор ребер с выбором корневой вершины образует дерево Тремо, в монадической логике второго порядка графов , а точнее в форме этой логики, называемой MSO ₂ , которая допускает квантификацию как по наборам вершин, так и по наборам ребер. Это свойство можно выразить как конъюнкцию следующих свойств: ${\displaystyle T}$ ${\displaystyle r}$

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

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

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

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

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

Деревья Тремо также играют ключевую роль в критерии планарности Фрейссе-Розенштиля для проверки того, является ли заданный граф планарным . Согласно этому критерию, граф является планарным, если для заданного дерева Тремо оставшиеся ребра могут быть размещены согласованным образом слева или справа от дерева, при условии соблюдения ограничений, которые не позволяют ребрам с одинаковым размещением пересекаться друг с другом. ^[11] ${\displaystyle G}$ ${\displaystyle T}$ ${\displaystyle G}$

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

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

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

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

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

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

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

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

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

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

Ссылки

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. Soukup, Lajos (2008), "Бесконечная комбинаторика: от конечного к бесконечному", Horizons of Combinatorics , Bolyai Soc. Math. Stud., т. 17, Berlin: Springer, стр. 189–213, doi :10.1007/978-3-540-77200-2_10, ISBN 978-3-540-77199-9, г-н  2432534. См. в частности теорему 3, стр. 193.
4. Diestel, Reinhard (2017), Теория графов, Graduate Texts in Mathematics, т. 173 (5-е изд.), Berlin: Springer, стр. 34–36, 220–221, 247, 251–252, doi :10.1007/978-3-662-53622-3, ISBN 978-3-662-53621-6, г-н  3644391
5. Рейф, Джон Х. (1985), «Поиск в глубину по своей сути последователен», Information Processing Letters , 20 (5): 229–234, doi :10.1016/0020-0190(85)90024-9, MR  0801987.
6. Aggarwal, A.; Anderson, RJ (1988), "Случайный алгоритм NC для поиска в глубину", Combinatorica , 8 (1): 1–12, doi :10.1007/BF02122548, MR  0951989, S2CID  29440871.
7. Каргер, Дэвид Р.; Мотвани , Раджив (1997), « Алгоритм NC для минимальных разрезов», SIAM Journal on Computing , 26 (1): 255–272, doi :10.1137/S0097539794273083, MR  1431256.
8. Курсель, Бруно (1996), «О выражении свойств графа в некоторых фрагментах монадической логики второго порядка» (PDF) , в Immerman, Neil ; Kolaitis, Phokion G. (ред.), Proc. Descr. Complex. Finite Models , DIMACS, т. 31, Amer. Math. Soc., стр. 33–62, MR  1451381.
9. Чартранд, Гэри ; Кронк, Хадсон В. (1968), «Случайно прослеживаемые графы», SIAM Journal on Applied Mathematics , 16 (4): 696–700, doi :10.1137/0116056, MR  0234852.
10. Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), "Глава 6. Деревья ограниченной высоты и глубины дерева", Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, т. 28, Гейдельберг: Springer, стр. 115–144, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, МР  2920058.
11. de Fraysseix, Hubert; Rosenstiehl, Pierre (1982), "Характеристика планарности с помощью поиска в глубину", Теория графов (Кембридж, 1981) , Ann. Discrete Math., т. 13, Амстердам: Северная Голландия, стр. 75–80, MR  0671906; де Фрейссекс, Юбер; Оссона де Мендес, Патрис ; Розенштиль, Пьер (2006), «Деревья Тремо и планарность», Международный журнал основ компьютерной науки , 17 (5): 1017–1029, arXiv : math/0610935 , doi :10.1142/S0129054106004248, MR  2270949.
12. Дистель, Рейнхард; Лидер, Имре (2001), «Нормальные остовные деревья, деревья Ароншайна и исключенные миноры» (PDF) , Журнал Лондонского математического общества , Вторая серия, 63 (1): 16–32, doi :10.1112/S0024610700001708, MR  1801714, S2CID  13980974.
13. Боулер, Натан; Гешке, Стефан; Питц, Макс (2016), Минимальные препятствия для нормальных остовных деревьев , arXiv : 1609.01042 , Bibcode : 2016arXiv160901042B
14. Diestel, Reinhard (2006), «Конечные пространства и остовные деревья», Журнал комбинаторной теории , Серия B, 96 (6): 846–854, CiteSeerX 10.1.1.63.9751 , doi : 10.1016/j.jctb.2006.02.010 , MR  2274079 .