Постановка задачи.

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

Цель данной работы - реализация алгоритма, вычисляющего минимальное остовное дерево.

Результатом работы программы должно быть получено множество рёбер минимального остовного дерева и замер времени вычисления.

Требуется реализовать последовательный и параллельный алгоритмы. Реализацию параллельного алгоритма провести средствами MPI.