Анализ алгоритма нахождения каркаса минимального веса: последовательная и параллельная реализации
Допустим, необходимо проложить кабель по территории университета, связав все его здания, так, чтобы из каждого здания кабель по какому-либо пути доходил до любого другого здания. Кроме того, предположим, что надо минимизировать общую длину прокладываемого кабеля. Если рассматривать здания как вершины, а кабели между зданиями как ребра, то эта работа с прокладыванием кабеля превращается в задачу определения каркаса, охватывающего здания территории университета, в котором общая длина проложенного кабеля должна быть минимальной. Такую задачу называют нахождением каркаса минимального веса.
Определим понятие каркаса более формально. Если дан связный неориентированный граф G=(V, E), то каркас (также называемый остовным или стягивающим деревом) T=(V, E’), где E’E – это связный граф без циклов. Иными словами, каркас неориентированного графа G – это подграф графа G, дерево, содержащее все вершины графа. Понятно, что для того, чтобы T имело тот же набор вершин, что и связный граф G, и чтобы T не имело циклов, оно должно содержать ровно |V|–1 ребро.
Предположим, что для каждого ребра eE существует вес w(e), причем такой вес может выражать, например, цену, длину или время, необходимое для прохода по ребру (в нашем примере – длину кабеля между зданиями). Во взвешенном графе вес подграфа – это сумма весов его ребер. Тогда каркас T минимального веса (или минимальное остовное дерево) – это каркас G, в котором вес дерева минимизирован относительно всех остовных деревьев G. Интуитивно определяется, что вес дерева T=(V, E’) равен




доставка по Москве и Московской области