Алгоритм построения минимального остовного дерева.

Остовное дерево связного нагруженного граф G с минимальной суммой длин содержащихся в нем ребер будем называть минимальным остовным деревом (МОД) графа G

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

Алгоритм ближайшего соседа для получения МОД . Возьмем произвольную вершину, выберем ближайшую к ней и включим обе вершины вместе с соединяющим их ребром в строящееся дерево. Затем найдем вершину, ближайшую к множеству из двух уже взятых вершин, и включим её вместе с соответствующим ребром в строящееся дерево, которое будет содержать уже 3 вершины и два ребра. Продолжаем действовать подобным образом, всякий раз включая ближайшую вершину к уже взятому множеству вершин вместе с соответствующим ребром, пока не получим остовного дерева. Докажем его оптимальность.

Будем для простоты считать веса всех ребер различными. Пусть с помощью алгоритма ближайшего соседа были последовательно получены ребра . Допустим противное, что имеется минимальное остовное дерево меньшего веса, в которое входят ребра , а ребро не входит , т.е. множество его ребер имеет вид , где среди ребер нет ребра . Поэтому добавление этого ребра приведет к появлению цикла. Пусть - множество вершин, связанных ребрами , - его дополнение. Ребро связывает множества и . Ясно, что в цикле должно присутствовать ещё хотя бы одно ребро, связывающее множества и и имеющее больший вес, чем вес ребра . Поэтому, удалив его из цикла, получим остовное дерево меньшего веса, что противоречит условию минимальности.

Нахождение вершины, ближайшей к множеству из вершин, требует элементарных операций, что при , близком к n/2, даст операций. Поэтому () — кратное повторение данной процедуры, осуществляемое при построении МОД по методу ближайшего соседа займет операций. Эту оценку, однако, можно понизить, если хранить список расстояний до строящегося дерева для всех не входящих в него вершин, а при каждом включении в дерево новой вершины обновлять список, просматривая лишь те не входящие в дерево вершины, которые смежныс вновь включенной. Такой просмотр требует операций и общая трудоемкость алгоритма становится .

Пример:

Определить МОД нагруженного графа G, изображенного на рисунке 41, используя алгоритм.

Решение.
25. Алгоритм перебора разрезов. Алгоритм нахождения минимального пути.

Сечением (разрезом) между вершинами i и j называется неизбыточный набор ребер, при удалении которых из графа теряется связь между данными вершинами (не существует пути из вершины iв вершину j). Заметим, что сечений между данными вершинами может быть много, и они могут содержать разное количество ребер.

Слово “неизбыточный” означает, что если любое ребро из сечения снова возвратить в граф, то связь восстановится.

Жадный алгоритм построения МОД. Упорядочим ребра графа в порядке неубывания весов и будем включать в подграф ребра по порядку, начиная с ребра наименьшего веса, следя за тем, чтобы включение очередного ребра не привело к появлению цикла. Если включение данного ребра приводит к появлению цикла, то оно пропускается и переходят к следующему по порядку ребру.

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

Если не принимать во внимание предварительное упорядочивание ребер, то при грамотной реализации данный алгоритм имеет трудоемкость .

Алгоритм Флоида.

Алгоритм Флойда. Этот алгоритм более общий по сравнению с др алгоритмами для задан-я поиска кратч. Пути м/у 2 вершин. Алгоримтфлойдаосн-н на Δ-операторе : Если расст d_ik>d_jk+d_ij,то d_ik= d_jk+d_ij (1)                          

РИСУНОК

Суть алгоритма:послед-ть действий.         ЭТАП 0: опред-м начальн матрицу расстояний Д₀ и матр

ершинS₀.Диагон-е элементы обеих матр делаем равными «_» означ-е что расст м/у верш i-i не сущ-т.                                                                             ОСНОВНОЙ ЭТАП k: задаем строку к и столбец к,как ведущ строку и ведущ столбец.Рассмотрим возможность применения Δ-оператора ко всем элементам d_ijматрицы Д_к-1.если выполн-сянер-во (1) при i≠j, j≠k, i≠k, то делаем след: а) строим матрД_к путем замены в матр Д_к-1кажд элемент d_ijсуммой d_ik+d_kj       б)строим матрицу S_k путем замены в матрS_k-1 = k. полагаем, что к=к+1. И повторяем этап к.

После реализации n –этапов алгоритма опред по матрицам Д_n и S_nкратч пути м/у узлами i и j. Матрица Д_n будет состоять из элементов d_ij-линиям расст между узлами i и j,а промежут-е узлы на пути от верш i к вершине j можно опред по матрице S_n.

Алгоритм Дейкстры.

Этот алгоритм предназначен для поиска кратчайшего пути между исходным заданным узлом и любым другим узлом сети. Поскольку алгоритм Флойда кратчайшего расстояния между любыми двумя узлами, то он является более общим чем алгоритм Дэикстры. В процессе выполнения алгоритма при переходе от i-ой вершины к j используются специальная процедура пометки ребер. Обозначим ui - кратчайшее расстояние от исходного узла 1-> «i» до узла i, через dij –длина ребра i-j, тогда для узла j определим метку j:[ ui,i] следующим образом :[ ui + dij ,i] для всех dij>0. Метки могут быть 2 типов : временные и постоянные. Временная может быть заменена на постоянную или на другую временную, если будет найден более короткий путь. Временная метка становится постоянный только в том случае когда станет очевидным, что не существует более короткого пути от исходного узла к рассматриваемому.

Схема алгоритма:

Этап 0. пусть вершина 1-исходный узел, тогда ей присваивается метка [0,-] , i:=1.

Этап 1. Рассматриваем какие узлы могут быть найдены исходя из узла 1. Присвоим им временные метки. Находим из этих меток наименьшее расстояние заменяем метку связанную с этим расстоянием на постоянную и переходим к этапу 2.

Этап k. Рассматриваем все узлы до которых можно попасть из узлов имеющих постоянные метки и если узел j имеет метку [uj,k], т.е. полученную от узла k и если ui + dij<uj , то метке [uj,k], замещается на [ui + dij,i]. Если все узлы имеют постоянные метки, то процесс заканчивается, иначе идем на этап k.

Комбинаторика.

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

Правила суммы и произведения: Если объект A может быть выбран n-способами, а объект B другими m-способами, при чём выборы объектов A и B несовместны, то выбор ''либо A либо B'' может быть выбран m+n способами.

Если объект A может быть выбран m-способами и после каждого из этих выборов объект B может быть выбран n способами, то выбор пары (A,B) может быть выбран m*n способами.

Правило степени. Если |А| = n, |В| = m, то |А^B| = n^m.

Если A – конечное множество, то |Aⁿ| = |A|ⁿ.

Пусть A содержит n-элементов, тогда:

Размещением из n элементов по m называют упорядоченноемн-во длины m, составленное из элементов мн-ва A. Размещение без повторений: A_n^m= n*(n-1)*…*(n-m+1). Размещение с повторениями: A_n^m= n^m

Перестановкой длины nназ-ся множество длины n, составленное из элементов мн-ва A: Pⁿ = n*(n-1)*…*(2)*(1)=n!

Сочетанием из n элементов по m наз-ся всевозможные комбинации из элементов мн-ва A длины m, т.е. C_n^m=A_n^m/ Pⁿ=n!/(m!*(n-m)!)