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

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

Жадный алгоритм построения МОД (Kruskal, 1956). Упорядочим ребра графа в порядке неубывания весов и будем включать в подграф ребра по порядку, начиная с ребра наименьшего веса, следя за тем, чтобы включение очередного ребра не привело к появлению цикла. Если включение данного ребра приводит к появлению цикла, то оно пропускается и переходят к следующему по порядку ребру.

Алгоритм начинает работу с пустого графа на n вершинах и на всех этапах имеет дело с лесом. При включении очередного ребра происходит слияние двух компонент связности и общее число компонент уменьшается на единицу. При включении - го ребра в результате слияния двух компонент леса возникает дерево, имеющее минимально возможный вес. Докажем это. Будем для простоты считать веса всех ребер различными. Пусть с помощью жадного алгоритма были последовательно получены ребра . Допустим противное, что имеется минимальное остовное дерево меньшего веса, в которое входят ребра , а ребро не входит , т.е. множество его ребер имеет вид , где среди ребер нет ребра . Тогда добавление этого ребра приведет к появлению цикла, в который войдет хотя бы одно из ребер . Имеем . Поэтому, удалив одно из ребер из цикла, получим остовное дерево меньшего веса, что противоречит условию минимальности

Если не принимать во внимание предварительное упорядочивание ребер, то при грамотной реализации данный алгоритм имеет трудоемкость .

Алгоритм ближайшего соседа для получения МОД (Prim, 1957). Возьмем произвольную вершину, выберем ближайшую к ней и включим обе вершины вместе с соединяющим их ребром в строящееся дерево. Затем найдем вершину, ближайшую к множеству из двух уже взятых вершин, и включим её вместе с соответствующим ребром в строящееся дерево, которое будет содержать уже 3 вершины и два ребра. Продолжаем действовать подобным образом, всякий раз включая ближайшую вершину к уже взятому множеству вершин вместе с соответствующим ребром, пока не получим остовного дерева. Докажем его оптимальность.

Будем для простоты считать веса всех ребер различными. Пусть с помощью алгоритма ближайшего соседа были последовательно получены ребра . Допустим противное, что имеется минимальное остовное дерево меньшего веса, в которое входят ребра , а ребро не входит , т.е. множество его ребер имеет вид , где среди ребер нет ребра . Поэтому добавление этого ребра приведет к появлению цикла. Пусть - множество вершин, связанных ребрами , - его дополнение. Ребро связывает множества и . Ясно, что в цикле должно присутствовать ещё хотя бы одно ребро, связывающее множества и и имеющее больший вес, чем вес ребра . Поэтому, удалив его из цикла, получим остовное дерево меньшего веса, что противоречит условию минимальности.

Нахождение вершины, ближайшей к множеству из вершин, требует элементарных операций, что при , близком к n/2, даст операций. Поэтому () – кратное повторение данной процедуры, осуществляемое при построении МОД по методу ближайшего соседа займет операций. Эту оценку, однако, можно понизить, если хранить список расстояний до строящегося дерева для всех не входящих в него вершин, а при каждом включении в дерево новой вершины обновлять список, просматривая лишь те не входящие в дерево вершины, которые смежны с вновь включенной. Такой просмотр требует операций и общая трудоемкость алгоритма становится .

Тест

1. Какие из алгоритмов нахождения МОД являются эффективными? а) только жадный алгоритм; б) только алгоритм ближайшего соседа; в) оба алгоритма.

2. Построение МОД методом ближайшего соседа следует начать а) с вершины минимальной степени; б) с вершины, инцидентной ребру минимального веса; в) можно начать с произвольной вершины.

3. Алгоритм построения МОД методом ближайшего соседа имеет трудоемкость а) ; б) ; в) .

Дата добавления: 2014-01-03