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

Пусть G(V,E) – связный нагруженный граф с p вершинами.

1. В качестве первого ребра искомого минимального каркаса выбираем ребро e1 с наименьшим весом μ(e1). Если таких рёбер несколько, то берем любое из них.

2. На каждом из следующих шагов добавляем самое короткое из оставшихся рёбер ei, при присоединении которого к уже выбранным рёбрам не образуется никакого цикла. Если имеется несколько рёбер одинаковой длины, то выбираем любое из них.

3. Указанный процесс продолжается до тех пор, пока к выбранному множеству рёбер нельзя добавить ребро без появления цикла. Полученный подграф и является минимальным каркасом исходного графа, и называется экономическим деревом.

 

 

Практика

Задача № 1. Для графов G1 и G2 построить графы G1ÈG2, G1ÇG2, G1(G2), G2(G1), матрицы смежности вершин А(G1), А(G2) и матрицы инцидентности В(G1), В(G2), введя предварительно нумерацию дуг. По матрицам смежности вершин исходных графов построить матрицы смежности вершин А(G1ÈG2), А(G1ÇG2), А(G1(G2)), А(G2(G1)). Будут ли изоморфны графы G1(G2) и G2(G1)?

 

 
 

 


Задача № 2. По алгоритму Краскала построить для нагруженного графа G, минимальный каркас G1 с указанием последовательности выбора рёбер ei. Определить вес построенного каркаса m(G1).

 

v2 v4

 

3 1 2 3

 

1 2 v3 3 v5 4 v8

 

v1 3 5 2 1

4 v6 v10 v9

v7


Задача о дороге

Успеет ли моя мама добраться из дома, который находится в пункте А, до вокзала, который находится в пункте Д, если поезд отправляется через час? На рисунке показано, какое время в минутах потрачено на дорогу из одного пункта в другой.


Лабиринт

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


 






Дата добавления: 2017-02-13; просмотров: 1482; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2021 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.01 сек.