Дерево Тремо

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

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

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

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

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

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

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

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

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

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

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

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

Нерешенная задача в информатике :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

^ Эвен, Шимон (2011), Графовые алгоритмы (2-е изд.), Cambridge University Press, стр. 46–48, ISBN 978-0-521-73653-4 .
^ Седжвик, Роберт (2002), Алгоритмы на C++: алгоритмы графов (3-е изд.), Pearson Education, стр. 149–157, ISBN 978-0-201-36118-6 .
^ Jump up to: Перейти обратно: ^а ^б ^с Соукуп, Лайош (2008), «Бесконечная комбинаторика: от конечного к бесконечному», Горизонты комбинаторики , Bolyai Soc. Математика. Студ., вып. 17, Берлин: Springer, стр. 189–213, номер документа : 10.1007/978-3-540-77200-2_10 , ISBN. 978-3-540-77199-9 , МР 2432534 . См., в частности, теорему 3, с. 193 .
^ Jump up to: Перейти обратно: ^а ^б ^с Дистель, Рейнхард (2017), Теория графов , Тексты для выпускников по математике, том. 173 (5-е изд.), Берлин: Springer, стр. 34–36, 220–221, 247, 251–252, doi : 10.1007/978-3-662-53622-3 , ISBN 978-3-662-53621-6 , МР 3644391
^ Рейф, Джон Х. (1985), «Поиск в глубину по своей сути является последовательным», Information Processing Letters , 20 (5): 229–234, doi : 10.1016/0020-0190(85)90024-9 , MR 0801987 .
^ Jump up to: Перейти обратно: ^а ^б Аггарвал, А.; Андерсон, Р.Дж. (1988), «Случайный алгоритм ЧПУ для поиска в глубину», Combinatorica , 8 (1): 1–12, doi : 10.1007/BF02122548 , MR 0951989 , S2CID 29440871 .
^ Каргер, Дэвид Р .; Мотвани, Раджив (1997), « Алгоритм ЧПУ для минимальных разрезов», SIAM Journal on Computing , 26 (1): 255–272, doi : 10.1137/S0097539794273083 , MR 1431256 .
^ Курсель, Бруно (1996), «О выражении свойств графа в некоторых фрагментах монадической логики второго порядка» (PDF) , Иммерман, Нил ; Колайтис, Фокион Г. (ред.), Proc. Описание Сложный. Конечные модели , DIMACS, вып. 31, амер. Математика. Соц., стр. 33–62, МР 1451381 .
^ Шартран, Гэри ; Кронк, Хадсон В. (1968), «Случайно отслеживаемые графики», SIAM Journal on Applied Mathematics , 16 (4): 696–700, doi : 10.1137/0116056 , MR 0234852 .
^ Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «Глава 6. Деревья ограниченной высоты и глубина дерева», Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Гейдельберг: Springer, стр. 115–144, номер документа : 10.1007/978-3-642-27875-4 , ISBN. 978-3-642-27874-7 , МР 2920058 .
^ де Фрессе, Юбер; Розенштиль, Пьер (1982), «Характеристика планарности с поиском в глубину», Теория графов (Кембридж, 1981) , Ann. Дискретная математика., вып. 13, Амстердам: Северная Голландия, стр. 75–80, MR 0671906 ; де Фрессе, Юбер; Оссона де Мендес, Патрис ; Розенштиль, Пьер (2006), «Деревья Тремо и планарность», Международный журнал основ компьютерных наук , 17 (5): 1017–1029, arXiv : math/0610935 , doi : 10.1142/S0129054106004248 , MR 2270949 .
^ Дистель, Рейнхард; Лидер, Имре (2001), «Нормальные остовные деревья, деревья Ароншайна и исключенные миноры» (PDF) , Журнал Лондонского математического общества , вторая серия, 63 (1): 16–32, doi : 10.1112/S0024610700001708 , MR 1801714 , S2CID 13980974 .
^ Боулер, Натан; Гешке, Стефан; Питц, Макс (2016), Минимальные препятствия для обычных остовных деревьев , arXiv : 1609.01042 , Bibcode : 2016arXiv160901042B
^ Jump up to: Перейти обратно: ^а ^б Дистель, Рейнхард (2006), «Конечные пространства и остовные деревья», Журнал комбинаторной теории , серия B, 96 (6): 846–854, CiteSeerX 10.1.1.63.9751 , doi : 10.1016/j.jctb.2006.02.010 , МР 2274079 .

[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 .

[soukoup-3] Jump up to: Перейти обратно: ^а ^б ^с Соукуп, Лайош (2008), «Бесконечная комбинаторика: от конечного к бесконечному», Горизонты комбинаторики , Bolyai Soc. Математика. Студ., вып. 17, Берлин: Springer, стр. 189–213, номер документа : 10.1007/978-3-540-77200-2_10 , ISBN. 978-3-540-77199-9 , МР 2432534 . См., в частности, теорему 3, с. 193 .

[diestel-4] Jump up to: Перейти обратно: ^а ^б ^с Дистель, Рейнхард (2017), Теория графов , Тексты для выпускников по математике, том. 173 (5-е изд.), Берлин: 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 .

[aa-6] Jump up to: Перейти обратно: ^а ^б Аггарвал, А.; Андерсон, Р.Дж. (1988), «Случайный алгоритм ЧПУ для поиска в глубину», Combinatorica , 8 (1): 1–12, doi : 10.1007/BF02122548 , MR 0951989 , S2CID 29440871 .

[7] Каргер, Дэвид Р .; Мотвани, Раджив (1997), « Алгоритм ЧПУ для минимальных разрезов», SIAM Journal on Computing , 26 (1): 255–272, doi : 10.1137/S0097539794273083 , MR 1431256 .

[8] Курсель, Бруно (1996), «О выражении свойств графа в некоторых фрагментах монадической логики второго порядка» (PDF) , Иммерман, Нил ; Колайтис, Фокион Г. (ред.), Proc. Описание Сложный. Конечные модели , DIMACS, вып. 31, амер. Математика. Соц., стр. 33–62, МР 1451381 .

[9] Шартран, Гэри ; Кронк, Хадсон В. (1968), «Случайно отслеживаемые графики», SIAM Journal on Applied Mathematics , 16 (4): 696–700, doi : 10.1137/0116056 , MR 0234852 .

[10] Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «Глава 6. Деревья ограниченной высоты и глубина дерева», Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Гейдельберг: Springer, стр. 115–144, номер документа : 10.1007/978-3-642-27875-4 , ISBN. 978-3-642-27874-7 , МР 2920058 .

[11] де Фрессе, Юбер; Розенштиль, Пьер (1982), «Характеристика планарности с поиском в глубину», Теория графов (Кембридж, 1981) , Ann. Дискретная математика., вып. 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

[d-14] Jump up to: Перейти обратно: ^а ^б Дистель, Рейнхард (2006), «Конечные пространства и остовные деревья», Журнал комбинаторной теории , серия B, 96 (6): 846–854, CiteSeerX 10.1.1.63.9751 , doi : 10.1016/j.jctb.2006.02.010 , МР 2274079 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]