МДК.01.02 Математический аппарат для проектирования компьютерных сетей

«Компьютерные сети»

Тема: Нахождение минимального остовного дерева
Цель работы: Приобрести навыки нахождения минимального остовного дерева
Норма времени: 2 часа.
После выполненных работ студент должен знать: определение маршрута, пути, цикла; алгоритм Краскала построения остовного дерева;
уметь: применять алгоритм Краскала для построения остовного дерева

Практическая работа № 4

заданного взвешенного неориентированного графа остовное дерево с наименьшей суммой

весов ребер — остовное дерево наименьшего веса.
1. Вначале текущее множество рѐбер устанавливается пустым.

Практическая работа № 4

рёбер, добавление которых к уже имеющемуся множеству не вызовет появление

в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству.
3. Когда таких рёбер больше нет, алгоритм завершён.

Практическая работа № 4

№ 4

так как образуется цикл.
Практическая работа № 4

так как образуется цикл.
Практическая работа № 4

и 7-8 (длина 8).
Можно выбирать любое, но только одно

(так как второе образует цикл).

Практическая работа № 4

найти минимальное остовное дерево для своего варианта графа.
Для каждого пункта

решения изобразить результат.
Ребра, которые выбирать запрещено, перечеркивать двойной линией.

остовного дерева
Вариант... (исходный рисунок графа)
Построение остовного дерева:
1. выбрано ребро, .

. , длина . . .
2. выбрано ребро, . . , длина . . .
. . .
N. выбрано ребро, . . , длина . . .