Построение минимального остовного дерева

2.                Построение минимального остовного дерева.

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

 

Шаг 0: C₀ = Ø,  = {1, 2, 3, 4, 5, 6, 7}

 

 

 

 

 

 

 

 

 

Шаг 1: C₁ = {1},  = {2, 3, 4, 5, 6, 7}

					8
	11		15
							3

 

 

 

Шаг 2: min l (1-2) = 5, j* = {2}, C₂ = {1, 2},  = {3, 4, 5, 6, 7}

Шаг 3: min l (2-3) = 4, j* = {3}, C₃ = {1, 2, 3},  = {4, 5, 6, 7}

 

 

 

 

 

 

 

 

 

 

Шаг 4: min l (3-4) = 2, j* = {4}, C₄ = {1, 2, 3, 4},  = {5, 6, 7}

 

 

 

 

 

 

 

 

Шаг 5: min l (4-5) = 3, j* = {5}, C₅ = {1, 2, 3, 4, 5},  = {6, 7}

 

 

 

 

 

 

 

Шаг 6: min l (5-6) = 8, j* = {6}, C₆ = {1, 2, 3, 4, 5, 6},  = {7}

 

 

 

 

 

 

 

 

 

 

Шаг 7: min l (6-7) = 3, j* = {7}, C₇ = {1, 2, 3, 4, 5, 6, 7},  = Ø

 

 

 

 

 

 

 

 

 

Минимальное остовное дерево будет выглядеть следующим образом:

 

 

 

 

 

Сумма весов ребер остовного дерева равна 5+4+2+3+8+3 = 25 ед.

 

Пример:

Необходимо соединить населенные пункты под номерами 1 – 7 автомобильными дорогами, при условии, что их протяженность будет минимальна.

Расстояния указаны рядом с каждым ребром сети.

Построение минимального остовного дерева решает эту задачу.

При этом протяженность автомобильных дорог, соединяющих все населенные пункты, будет равна 25 километрам.

3.                Нахождение кратчайшего маршрута.

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

Шаг 1: Начальная точка {1}.

Находим кратчайший маршрут до следующей точки.

 

 

 

 

 

 

 

 

 

Шаг 2: Точки {1} и {2} соединяем кратчайшим маршрутом со следующей точкой.

 

 

 

 

 

 

 

 

 

Шаг 3: Точки {1} и {3} соединяем кратчайшим маршрутом со следующей точкой.

 

 

 

 

 

 

 

 

 

В результате получаем два альтернативных пути – один из них обозначен пунктиром.

Шаг 4: Точку {4} соединяем кратчайшим маршрутом со следующей точкой.

 

 

 

 

 

 

 

 

 

Шаг 5: Точки {4} и {5} соединяем кратчайшим маршрутом со следующей точкой.

 

 

 

 

 

 

 

 

 

 

 

Шаг 6: Точки {4} и {6} соединяем кратчайшим маршрутом со следующей точкой.

 

 

 

 

 

 

 

 

 

В результате итераций мы нашли кратчайшие маршруты, записанные ниже в таблицу 2.

Таблица 2

Узел сети	Кратчайший маршрут
	топология	протяженность
2	1-2	5
3	1-2-3	9
4	1-2-3-4 или 1-4	11
5	1-2-3-4-5 или 1-4-5	14
6	1-2-3-4-5-6 или 1-4-5-6	22
7	1-2-3-4-5-6-7 или 1-4-5-6-7	25

 

Пример:

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

С помощью алгоритма построения кратчайшего маршрута такой тип задачи можно решить. В результате расчетов минимальное время в пути будет составлять 25 часов.