Минимальные остовные деревья

одели графов, в которых мы связываем веса (weights) или стоимости (costs) с каждым ребром, используются во многих приложениях. В картах авиалиний, в которых реб­рами отмечены авиарейсы, такие веса означают расстояния или стоимость проезда. В электронных схемах, где ребра представляют электрические соединения, веса могут означать длину соединения, его стоимость или время, необходимое для распространения по ней сигнала. В задачах календарного планирования веса могут представлять время или расходы, затрачиваемые на выполнение задач, либо время ожидания завершения соответствующей задачи.

Естественно, в таких ситуациях возникают вопросы, ка­сающиеся различных аспектов минимизации стоимости. Мы будем изучать алгоритмы решения двух задач такого рода: (i) определение пути с наименьшей стоимостью, соединяюще­го все точки, и (ii) отыскание пути наименьшей стоимости, соединяющего две заданных точки. Первый тип алгоритма применяется для решения задач на неориентированных гра­фах, которые представляют такие объекты как электричес­кие цепи, находит минимальное остовное дерево (minimum spanning tree); это дерево является основной темой данной главы. Второй тип алгоритма, применяемый для решения за­дач на орграфах, которые представляют такие объекты, как карты авиарейсов, определяет кратчайшие пути (shortest path), и они являются темой обсуждений в главе 21. Эти алгорит­мы находят широкое применение не только в приложениях, связанных со схемами авиарейсов и электрическими схема­ми, они используются также и при решении задач, возника­ющих во взвешенных графах.

Когда мы изучаем алгоритмы обработки взвешенных гра­фов, наша интуиция часто отождествляет веса с расстояни-

Часть 5. Алгоритмы на графах

ями: мы употребляем выражение " ближайшая к х верши­на" и ему подобные. Действительно, термин " кратчай­ший путь" оказывается в русле этой тенденции. Однако, несмотря на многочисленные приложения, в которых мы по существу имеем дело с расстояниями, и несмотря на все преимущества геометрической интуиции в понима­нии базовых алгоритмов, важно помнить, что веса не обязательно должны быть пропорциональны расстоянию, они могут представлять время и стоимость или совсем другую переменную величину. В самом деле, как мы убе­димся в главе 21, веса в условиях задач определения крат­чайшего пути могут принимать даже отрицательные зна­чения.

Прибегая к помощи интуиции при описании алгорит­мов и примеров и сохраняя при этом общую примени­мость, мы используем неоднозначные термины, когда попеременно ссылаемся на длины и веса. В большей ча­сти примеров, приводимых в настоящей главе, мы ис­пользуем веса, пропорциональные расстоянию между вершинами, как это нетрудно видеть на рис. 20.1. Такие графы удобно рассматривать в качестве примеров, по­скольку нет необходимости указывать метки ребер, ибо достаточно одного взгляда, дабы уяснить, что более длин­ные ребра имеют большие веса по сравнению с корот­кими ребрами. Когда веса представляет расстояния, мы получаем возможность рассматривать алгоритмы, кото­рые становятся более эффективными, когда учитывают

РИСУНОК 20.1. ВЗВЕШЕННЫЙ НЕОРИЕНТИРОВАННЫЙ ГРАФ И ЕГО ДЕРЕВО MST

Взвешенный неориентированный граф представляет собой набор взвешенных ребер. Дерево MST есть множество ребер минималь­ного общего веса, которые соединяют все вершины (выделе­ны черным в списке ребер, утолщенные ребра на чертеже графа). В рассматриваемом графе веса пропорциональны расстояниям между вершинами, однако базовые алгоритмы, которые мы исследуем, соответ­ствуют графам общего вида и не накладывают никаких условий на веса (см. рис. 20.2).