Остовное дерево - Spanning tree

Для сетевого протокола см. Протокол связующего дерева. Для использования в других целях см. Spanning tree (значения).
Остовное дерево (синие тяжелые края) сетка графика

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

Приложения

Несколько Найти путь алгоритмы, в том числе Алгоритм Дейкстры и Алгоритм поиска A *, внутренне построить связующее дерево в качестве промежуточного шага в решении проблемы.

Чтобы свести к минимуму стоимость электрических сетей, проводных соединений, трубопроводов, автоматического распознавания речи и т. Д., Люди часто используют алгоритмы, которые постепенно строят остовное дерево (или множество таких деревьев) в качестве промежуточных шагов в процессе поиска минимальное остовное дерево.[1]

Интернет и многое другое телекоммуникационные сети имеют каналы передачи, которые соединяют узлы вместе в топология сетки который включает в себя несколько петель. Чтобы "избежать мостиковые петли и "петли маршрутизации ", многие протоколы маршрутизации, разработанные для таких сетей, включая Протокол связующего дерева, Сначала откройте кратчайший путь, Протокол маршрутизации по состоянию канала, Расширенная маршрутизация на основе дерева и т. д. - требуют, чтобы каждый маршрутизатор запомнил связующее дерево.

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

Определения

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

Фундаментальные циклы

Добавление только одного ребра к остовному дереву создаст цикл; такой цикл называется основной цикл. Для каждого ребра, не входящего в остовное дерево, существует отдельный фундаментальный цикл; таким образом, существует взаимно однозначное соответствие между фундаментальными циклами и ребрами не в остовном дереве. Для связного графа с V вершин, любое остовное дерево будет иметь V - 1 ребро, а значит, граф E ребра и одно из его остовных деревьев будут иметь E − V + 1 фундаментальный цикл (количество ребер, вычтенное на количество ребер, включенных в остовное дерево; дающее количество ребер, не включенных в остовное дерево). Для любого данного остовного дерева множество всех E − V + 1 фундаментальный цикл образует основа цикла, основа для велосипедное пространство.[3]

Фундаментальные сокращения

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

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

Охватывающие леса

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

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

Чтобы избежать путаницы между этими двумя определениями, Гросс и Йеллен (2005) предложить термин "полный покрывающий лес" для покрывающего леса с той же связью, что и данный граф, а Бонди и Мурти (2008) вместо этого назовите этот вид леса «лесом максимального охвата».[8]

Подсчет остовных деревьев

Формула Кэли подсчитывает количество остовных деревьев на полном графе. Есть деревья в , деревья в , и деревья в .

Номер т(грамм) остовных деревьев связного графа является хорошо изученной инвариантный.

В конкретных графиках

В некоторых случаях легко вычислить т(грамм) напрямую:

  • Если грамм сам по себе дерево, то т(грамм) = 1.
  • Когда грамм это график цикла Cп с п вершины, то т(грамм) = п.
  • Для полный график с п вершины, Формула Кэли[9] дает количество остовных деревьев как пп − 2.
  • Если грамм это полный двудольный граф ,[10] тогда .
  • Для п-размерный граф гиперкуба ,[11] количество остовных деревьев .

В произвольных графах

Основная статья: Теорема Кирхгофа

В общем, для любого графика грамм, номер т(грамм) можно рассчитать в полиномиальное время как детерминант из матрица полученный из графика, используя Теорема Кирхгофа о матричном дереве.[12]

В частности, для вычисления т(грамм), строится квадратная матрица, в которой строки и столбцы индексируются вершинами грамм. Запись в строке я и столбец j это одно из трех значений:

  • Степень вершины я, если я = j,
  • −1, если вершины я и j смежные, или
  • 0, если вершины я и j отличаются друг от друга, но не смежными.

Результирующая матрица единственное число, поэтому его определитель равен нулю. Однако удаление строки и столбца для произвольно выбранной вершины приводит к меньшей матрице, определитель которой точно равент(грамм).

Удаление-сокращение

Если грамм это график или мультиграф и е - произвольное ребро грамм, то число т(грамм) остовных деревьев грамм удовлетворяет повторение удаления-сокращеният(грамм) = т(грамм − е) + т(грамм/е), куда грамм − е мультиграф, полученный удалением еи грамм/е это сокращение из грамм к е.[13] Период, термин т(грамм − е) в этой формуле считает остовные деревьяграмм которые не используют крайе, а срок т(грамм/е) считает остовные деревьяграмм это использованиее.

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

Полином Тутте

Основная статья: Полином Тутте

В Полином Тутте Графа можно определить как сумму по остовным деревьям графа терминов, вычисленных на основе «внутренней активности» и «внешней активности» дерева. Его значение в аргументах (1,1) - это количество остовных деревьев или, в несвязном графе, количество максимальных остовных лесов.[14]

Многочлен Тутте также можно вычислить с использованием рекуррентности удаления-сокращения, но его вычислительная сложность высокий: для многих значений его аргументов его точное вычисление # P-complete, а также трудно приблизиться к гарантированной коэффициент аппроксимации. Точка (1,1), в которой его можно вычислить с помощью теоремы Кирхгофа, является одним из немногих исключений.[15]

Алгоритмы

Строительство

Одно остовное дерево графа можно найти в линейное время либо поиск в глубину или же поиск в ширину. Оба эти алгоритма исследуют данный граф, начиная с произвольной вершины. v, путем перебора соседей обнаруженных вершин и добавления каждого неисследованного соседа в структуру данных, которая будет исследована позже. Они различаются тем, является ли эта структура данных куча (в случае поиска в глубину) или очередь (в случае поиска в ширину). В любом случае можно сформировать остовное дерево, соединив каждую вершину, кроме корневой. v, в вершину, из которой он был обнаружен. Это дерево известно как дерево поиска в глубину или дерево поиска в ширину в соответствии с алгоритмом исследования графа, использованным для его построения.[16] Деревья поиска в глубину являются частным случаем класса остовных деревьев, называемых Деревья Тремо, названный в честь первооткрывателя XIX века поисков в глубину.[17]

Связующие деревья важны в параллельных и распределенных вычислениях как способ поддержания связи между набором процессоров; см., например, Протокол связующего дерева использован Канальный уровень OSI устройства или Крик (протокол) для распределенных вычислений. Однако методы «в глубину» и «в ширину» для построения покрывающих деревьев на последовательных компьютерах плохо подходят для параллельных и распределенных компьютеров.[18] Вместо этого исследователи разработали несколько более специализированных алгоритмов для поиска остовных деревьев в этих моделях вычислений.[19]

Оптимизация

В некоторых областях теории графов часто бывает полезно найти минимальное остовное дерево из взвешенный график. Также были изучены другие проблемы оптимизации остовных деревьев, включая максимальное остовное дерево, минимальное дерево, охватывающее не менее k вершин, остовное дерево с наименьшим количеством ребер на вершину, то остовное дерево с наибольшим количеством листьев, остовное дерево с наименьшим количеством листьев (тесно связанное с Гамильтонова проблема пути ), остовное дерево минимального диаметра и остовное дерево минимального расширения.[20][21]

Задачи оптимального остовного дерева также изучались для конечных наборов точек в геометрическом пространстве, таком как Евклидова плоскость. Для таких входных данных остовное дерево снова является деревом, вершинами которого являются заданные точки. Качество дерева измеряется так же, как и на графике, с использованием евклидова расстояния между парами точек в качестве веса для каждого ребра. Так, например, Евклидово минимальное остовное дерево то же самое, что и минимальное остовное дерево графа в полный график с евклидовыми весами ребер. Однако нет необходимости строить этот граф для решения задачи оптимизации; проблема евклидова минимального остовного дерева, например, может быть решена более эффективно в О(п бревноп) время, построив Триангуляция Делоне а затем применяя линейное время планарный граф алгоритм минимального остовного дерева для результирующей триангуляции.[20]

Рандомизация

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

Альтернативной моделью для генерации остовных деревьев случайным образом, но не равномерно является случайное минимальное остовное дерево. В этой модели ребрам графа присваиваются случайные веса, а затем минимальное остовное дерево взвешенного графа.[23]

Перечисление

Поскольку граф может иметь экспоненциально много остовных деревьев, перечислить их все в полиномиальное время. Однако известны алгоритмы для перечисления всех покрывающих деревьев за полиномиальное время для каждого дерева.[24]

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

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

Деревья внутри графа могут быть частично упорядочены их отношением подграфа, и любая бесконечная цепь в этом частичном порядке имеет верхнюю границу (объединение деревьев в цепочке). Лемма Цорна, одно из многих эквивалентных утверждений выбранной аксиомы, требует, чтобы частичный порядок, в котором все цепи ограничены сверху, имел максимальный элемент; в частичном порядке на деревьях графа этот максимальный элемент должен быть остовным деревом. Следовательно, если предположить лемму Цорна, каждый бесконечный связный граф имеет остовное дерево.[25]

В другом направлении, учитывая семейство наборов, можно построить бесконечный граф такой, что каждому остовному дереву графа соответствует функция выбора семейства наборов. Следовательно, если каждый бесконечный связный граф имеет остовное дерево, то выбранная аксиома верна.[26]

В направленных мультиграфах

Идея остовного дерева может быть обобщена на ориентированные мультиграфы.[27] Учитывая вершину v на ориентированном мультиграфе грамм, ориентированное остовное дерево Т укорененный в v является ациклическим подграфом грамм в котором каждая вершина кроме v имеет исходящую степень 1. Это определение выполняется только тогда, когда "ветви" Т указать на v.

Смотрите также

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

  1. ^ Graham, R.L .; Ад, Павол (1985). "К истории проблемы минимального остовного дерева" (PDF).
  2. ^ Бейнеке, Лоуэлл В.; Уилсон, Робин Дж. (2009), Темы топологической теории графов, Энциклопедия математики и ее приложений, 128, Cambridge University Press, Кембридж, стр. 36, Дои:10.1017 / CBO9781139087223, ISBN  978-0-521-80230-7, МИСТЕР  2581536
  3. ^ Коджай и Крехер (2004) С. 65–67.
  4. ^ Коджай и Крехер (2004) С. 67–69.
  5. ^ Оксли, Дж. Г. (2006), Матроид Теория, Оксфорд Тексты для выпускников по математике, 3, Oxford University Press, стр. 141, ISBN  978-0-19-920250-8.
  6. ^ Боллобаш, Бела (1998), Современная теория графов, Тексты для выпускников по математике, 184, Springer, стр. 350, ISBN  978-0-387-98488-9; Мельхорн, Курт (1999), LEDA: платформа для комбинаторных и геометрических вычислений, Cambridge University Press, стр. 260, ISBN  978-0-521-56329-1.
  7. ^ Кэмерон, Питер Дж. (1994), Комбинаторика: темы, методы, алгоритмы, Cambridge University Press, стр. 163, ISBN  978-0-521-45761-3.
  8. ^ Гросс, Джонатан Л .; Йеллен, Джей (2005), Теория графов и ее приложения (2-е изд.), CRC Press, стр. 168, ISBN  978-1-58488-505-4; Bondy, J. A .; Мурти, США (2008), Теория графов, Тексты для выпускников по математике, 244, Springer, стр. 578, ISBN  978-1-84628-970-5.
  9. ^ Айгнер, Мартин; Циглер, Гюнтер М. (1998), Доказательства из КНИГИ, Springer-Verlag, стр. 141–146.
  10. ^ Хартсфилд, Нора; Рингель, Герхард (2003), Жемчуг в теории графов: всестороннее введение, Courier Dover Publications, п. 100, ISBN  978-0-486-43232-8.
  11. ^ Харари, Фрэнк; Hayes, John P .; Ву, Хорнг-Джих (1988), "Обзор теории графов гиперкуба", Компьютеры и математика с приложениями, 15 (4): 277–289, Дои:10.1016/0898-1221(88)90213-1, HDL:2027.42/27522, МИСТЕР  0949280.
  12. ^ Коджай, Уильям; Креер, Дональд Л. (2004), "5.8 Теорема о матричном дереве", Графики, алгоритмы и оптимизация, Дискретная математика и ее приложения, CRC Press, стр. 111–116, ISBN  978-0-203-48905-5.
  13. ^ Коджай и Крехер (2004), п. 109.
  14. ^ Боллобаш (1998), п. 351.
  15. ^ Гольдберг, Л.А.; Джеррам, М. (2008), "Неприближаемость полинома Тутте", Информация и вычисления, 206 (7): 908–929, arXiv:cs / 0605140, Дои:10.1016 / j.ic.2008.04.003; Jaeger, F .; Vertigan, D. L .; Валлийский, Д. Дж. А. (1990), "О вычислительной сложности многочленов Джонса и Тутте", Математические труды Кембриджского философского общества, 108: 35–53, Дои:10.1017 / S0305004100068936.
  16. ^ Козен, Декстер (1992), Дизайн и анализ алгоритмов, Монографии по информатике, Springer, стр. 19, ISBN  978-0-387-97687-7.
  17. ^ де Фрейссе, Юбер; Розенштиль, Пьер (1982), "Характеристика планарности методом поиска в глубину", Теория графов (Кембридж, 1981), Анна. Дискретная математика., 13, Амстердам: Северная Голландия, стр. 75–80, МИСТЕР  0671906.
  18. ^ Рейф, Джон Х. (1985), «Поиск в глубину по своей сути является последовательным», Письма об обработке информации, 20 (5): 229–234, Дои:10.1016/0020-0190(85)90024-9, МИСТЕР  0801987.
  19. ^ Gallager, R.G .; Humblet, P.A .; Спира, П. М. (1983), "Распределенный алгоритм для остовных деревьев минимального веса", Транзакции ACM по языкам и системам программирования, 5 (1): 66–77, Дои:10.1145/357195.357200; Газит, Хиллель (1991), "Оптимальный рандомизированный параллельный алгоритм для поиска связных компонентов в графе", SIAM Журнал по вычислениям, 20 (6): 1046–1067, Дои:10.1137/0220066, МИСТЕР  1135748; Бадер, Дэвид А .; Конг, Гоцзин (2005), «Быстрый параллельный алгоритм связующего дерева для симметричных мультипроцессоров (SMP)» (PDF), Журнал параллельных и распределенных вычислений, 65 (9): 994–1006, Дои:10.1016 / j.jpdc.2005.03.011.
  20. ^ а б Эппштейн, Дэвид (1999), «Острова и гаечные ключи» (PDF), в Sack, J.-R.; Уррутия, Дж. (ред.), Справочник по вычислительной геометрии, Elsevier, стр. 425–461..
  21. ^ Ву, Банг Е; Чао, Кунь-Мао (2004), Связующие деревья и проблемы оптимизации, CRC Press, ISBN  1-58488-436-3.
  22. ^ Уилсон, Дэвид Брюс (1996), «Генерация случайных остовных деревьев быстрее, чем время покрытия», Материалы двадцать восьмого ежегодного симпозиума ACM по теории вычислений (STOC 1996), стр. 296–303, Дои:10.1145/237814.237880, МИСТЕР  1427525.
  23. ^ МакДиармид, Колин; Джонсон, Теодор; Стоун, Гарольд С. (1997), «О нахождении минимального остовного дерева в сети со случайными весами» (PDF), Случайные структуры и алгоритмы, 10 (1–2): 187–204, Дои:10.1002 / (SICI) 1098-2418 (199701/03) 10: 1/2 <187 :: AID-RSA10> 3.3.CO; 2-Y, МИСТЕР  1611522.
  24. ^ Габоу, Гарольд Н .; Майерс, Юджин В. (1978), "Нахождение всех остовных деревьев ориентированных и неориентированных графов", SIAM Журнал по вычислениям, 7 (3): 280–287, Дои:10.1137/0207024, МИСТЕР  0495152
  25. ^ а б Серр, Жан-Пьер (2003), Деревья, Монографии Спрингера по математике, Springer, p. 23.
  26. ^ Соукуп, Лайош (2008), «Бесконечная комбинаторика: от конечного к бесконечному», Горизонты комбинаторики, Bolyai Soc. Математика. Stud., 17, Берлин: Springer, стр. 189–213, Дои:10.1007/978-3-540-77200-2_10, МИСТЕР  2432534. См., В частности, теорему 2.1, стр. 192–193.
  27. ^ Левин, Лайонел (2011). «Группы песочницы и остовные деревья ориентированных линейных графов». Журнал комбинаторной теории, серия А. 118 (2): 350–364. arXiv:0906.2809. Дои:10.1016 / j.jcta.2010.04.001. ISSN  0097-3165.