Цель работы. Сформировать у студентов знания, умения и навыки нахождения минимального остовного дерева в математическом пакете mathсad

Сформировать у студентов знания, умения и навыки нахождения минимального остовного дерева в математическом пакете MathСad.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Изучите теоретическую часть. Выполните задание, соответствующее номеру Вашего варианта, и продемонстрируйте его преподавателю.

2. Оформите отчет по лабораторной работе, который должен содержать:

· титульный лист (Рис. 2);

· исходные данные варианта;

· последовательность действий для решения задачи;

· результаты решения задачи.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Минимальным остовным деревом связного взвешенного графа называется его связный подграф, состоящий из всех вершин исходного дерева и некоторых его ребер, причем сумма весов ребер минимально возможная. Задача о нахождении минимального остовного дерева часто встречается в подобной постановке: есть n городов, через которые можно проложить маршрут так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Требуется найти такой маршрут, чтобы стоимость проезда была минимальной.