Автор работы: Пользователь скрыл имя, 30 Марта 2013 в 15:43, доклад
Минимальным остовным деревом (МОД) связного взвешенного графа называется его связный подграф, состоящий из всех вершин исходного дерева и некоторых его ребер, причем сумма весов ребер максимально возможная. Если исходный граф несвязен, то описываемую, ниже процедуру можно применять поочередно к каждой его компоненте связности, получая тем самым минимальные остовные деревья для этих компонент.
Введение.
Нахождение кратчайших путей в графе.
Описание алгоритма Краскала.
Псевдокод алгоритма.
Блок-схема алгоритма.
Оценка сложности алгоритма и пример.
Вывод.
Список использованной литературы.