Минимальное остовное дерево
Ряд задач из теории графов называется "Минимальное охватывающее дерево". В теории графов дерево - это способ соединить все вершины вместе, так что существует ровно один путь от любой одной вершины до любой другой вершины дерева. Если на графике представлено несколько городов, соединённых дорогами, то можно выбрать такое количество дорог, чтобы до каждого города можно было добраться из одного города в другой, но чтобы было не более одного пути из одного города в другой.
График может иметь более одного пролетного дерева, так же как и может быть более одного способа выбора дорог между городами.
Большую часть времени, графики взвешены; каждое соединение между двумя городами имеет вес: это может стоить чего-то, чтобы путешествовать по данной дороге, или одно соединение может быть длиннее, чем другое, это означает, что требуется больше времени, чтобы путешествовать по этому соединению. В языке теории графов соединения называются краями.
Минимальное охватывающее дерево - это дерево. Оно отличается от других деревьев тем, что минимизирует общий вес, прикрепленный к краям. В зависимости от того, как выглядит график, может быть более одного минимального пролетного дерева. В графе, где все ребра имеют одинаковый вес, каждое дерево является минимальным охватывающим деревом. Если все ребра имеют разный вес (т.е. нет двух ребер с одинаковым весом), то существует ровно одно минимальное дерево.
Минимальное охватывающее дерево планарного графика. На каждой кромке наклеивается этикетка с указанием ее веса, который здесь приблизительно пропорционален ее длине.
Поиск минимального пролетающего дерева
Первая попытка
Может быть очень просто сделать алгоритм, который обнаружит минимальное охватывающее дерево:
функция MST(G,W) : T = {} , в то время как T не образует пролетное дерево: найти минимально взвешенную кромку в E, которая безопасна для T T = T объединения {(u,v) } return TВ этом случае "безопасно" означает, что включение края не образует цикла на графике. Цикл означает, что цикл начинается с вершины, переходит в ряд других вершин и заканчивается снова в начальной точке без повторного использования одной и той же ребра.
История
В 1926 году чешский ученый Отакар Борувка разработал первый известный алгоритм поиска минимального пролетающего дерева. Он хотел решить проблему поиска эффективного покрытия Моравии электричеством. Сегодня этот алгоритм известен как алгоритм Борувки. Сегодня широко используются еще два алгоритма. Один из них был разработан Войтехом Ярником в 1930 году и внедрен на практике Робертом Глиной Примом в 1957 году. Эдсгер Вайбе Дийкстра заново открыл его в 1959 году и назвал алгоритмом Прима. Другой алгоритм называется алгоритмом Крускала, и был отработан Иосифом Крускалом в 1956 году. Все три алгоритма жадные и работают в полиномиальном времени.
Самый быстрый алгоритм минимальной длины дерева на сегодняшний день был разработан Бернардом Шазель. Алгоритм основан на мягкой куче, приблизительной очереди приоритетов. Его время работы - O(m α(m,n)), где m - число рёбер, n - число вершин и α - классическая функциональная обратная функция Акермана. Функция α растет чрезвычайно медленно, так что для всех практических целей ее можно считать константой не больше 4; таким образом, алгоритм Шацеля занимает очень близкое к линейному время.
Какой самый быстрый алгоритм для этой проблемы? Это один из старейших открытых вопросов в компьютерной науке. Очевидно, что существует линейная нижняя граница, так как мы должны хотя бы рассмотреть все веса. Если граничные веса - это целые числа с ограниченной длиной бита, то детерминистические алгоритмы известны с линейным временем выполнения. Для общих весов существуют рандомизированные алгоритмы, чье ожидаемое время работы является линейным.
Проблема также может быть решена распределенным образом. Если каждый узел считается компьютером и ни один из узлов не знает ничего, кроме своих собственных подключенных связей, то все равно можно вычислить распределенное минимальное дерево пролетов.
Вопросы и ответы
В: Что такое минимальное остовное дерево в теории графов?
О: Минимальное охватывающее дерево - это дерево, которое минимизирует суммарные веса, приложенные к ребрам в теории графов.
В: Что такое дерево в теории графов?
О: Дерево - это способ соединения всех вершин вместе в теории графов таким образом, что существует только один путь от любой вершины к любой другой вершине дерева.
В: Какова цель выбора дорог в сценарии теории графов, представляющем города?
О: Цель выбора дорог в сценарии теории графов, представляющем города, состоит в том, чтобы каждый город был доступен из любого другого города, но при этом не было более одного возможного пути из одного города в другой.
В: Может ли граф иметь более одного дерева огибающей?
О: Да, у графа может быть более одного связующего дерева.
В: В чем разница между минимальным остовным деревом и другими деревьями в теории графов?
О: Минимальное охватывающее дерево минимизирует суммарные веса, прикрепленные к ребрам, в то время как другие деревья не обладают этой особенностью.
В: Что такое ребра в теории графов?
О: Ребра - это связи между двумя вершинами в теории графов.
В: Может ли существовать более одного минимального охватывающего дерева в графе с различными взвешенными ребрами?
О: Да, в зависимости от того, как выглядит граф, может существовать более одного минимального проходящего дерева.
