Курсовая работа: Использование математических методов и моделей в управлении микроэкономическими системами

2

(4, 5)

3

(4, 7)

15

(5, 6)

8

(6, 7)

3

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 автомобильными дорогами, при условии, что их протяженность будет минимальна.