Алгоритм Прима – Краскала. Применение алгоритма при оптимизации проектных решений

1.1.33 вопросы

Алгоритм Прима – Краскала.

Остов графа –(остовное дерево) покрывающее дерево, каркас графа – это дерево содержащее все вершины графа(покрывающее все вершины графа).

Min дерево остовное или кратчайший остов – это то дерево покрывает все вершины и имеет минимальный суммарный вес  входящих в него ребер.

Для определения минимального остовного дерева используюа алгоритм, кот. Наз- ся алгоритм Прима- Краскала. Он состоит из схожих алгоритмов Прима и Краскала. Различают 3 разновидности.

1- я разновидность: Состоит из 2- х шагов.

1.Шаг: Упорядочить ребра графа по убыванию весов (т.е. постоить некоторый численный ряд).

2. Шаг: Рассмотреть последовательно все ребра начиная с ребра наибольшего веса и определить можно ли их удалить из графа не нарушив его связности (т.е. определить есть ли еще путь не считая пути через удаляемое ребро, по кот. Можно пройти от одной до другой вершины данного ребра).

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

2- я разновидность:

1 шаг: Упорядочить ребра графа по возрастанию весов начиная с минимального.

2- шаг: В соответствии с рядом чисел в составе шага «1» последовательно решить вопрос включить ли в остовное  дерево новое ребро. Первое ребро включается в дерево обязательно. Если при таком включении может образоваться цикл, то ребро не включается.

Полученное остовное дерево имеет минимальный вес ребер.

3- я разновидность:

Предназначена специально для многопроцессорных машин.

1 шаг: Каждый процессор выхватывает из предложенного графа 1 цикл и выбрасывает из цикла ребро с наибольшим весом (если таких ребер несколько, то выбрасывается одно, и тогда дерево имеет минимальный вес ребер)

Модифицированный алгоритм Прима-Краскала

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

Вообще дерево это частный случай связывающей сети при связности равной единице.

Модифицированный алгоритм распространяется на связывающие сети у кот. связность может быть больше 1.

1 шаг: Упорядочить ребра графа по убыванию весов (т.е. построить некоторый численный ряд).

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

Суммарный вес оставшихся ребер- минимальный.

*Примечание: При связности больше единицы кратчайшая связывающая цепь может содержать цикл. Это исключено при связности равной единице, т.к. там получаем дерево.

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

   Применение алгоритма при оптимизации проектных решений.

Задача о минимальном остовном дереве заданного взвешенного связного графа G состоит в нахождение связного остовного подграфа минимального веса. В практическом виде эта задача часто решается при построении кратчайшей коммутационной сети.

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