Cтраница 2
Алгоритм нахождения кратчайшего пути, который применим к графу с ребрами произвольной длины, а также алгоритм построения стягивающего дерева с минимальной стоимостью ( который является усовершенствованием второго алгоритма из разд. [16]
Рассматриваемый алгоритм несколько необычен для комбинаторных алгоритмов: отталкиваясь от произвольно выбранного начального стягивающего дерева, он ведет прямо к стягивающему дереву минимальной стоимости. Когда окажется, что совершить очередную замену невозможно, имеется гарантия, что найдено стягивающее дерево минимальной стоимости. Так происходит потому, что в пространстве стягивающих деревьев отсутствуют локальные минимумы, из которых нужно было бы выбираться для достижения абсолютного минимума. [17]
Наша задача состоит в разбиении множества ребер G на два таких класса, чтобы ребра, принадлежащие одному из классов, образовали стягивающее дерево, причем их общая стоимость была бы не больше стоимости любого другого стягивающего дерева. Предположим, что для начала у нас есть некоторое стягивающее дерево; наш алгоритм будет состоять в последовательности замен, при которых к этому дереву добавляется ребро, ранее ему не принадлежавшее, а некоторое ребро выбрасывается. [18]
Граф задает нейтральную игру тогда и только тогда, когда после добавления ребра, соединяющего две выделенные его вершины, он распадается на два стягивающих дерева, не имеющих общих ребер. [19]
Один ( не очень существенный) недостаток изложенного алгоритма для построения минимального стягивающего дерева состоит в предположении, что с самого начала у нас уже есть по крайней мере одно стягивающее дерево. С другой стороны, если сначала нужно построить стягивающее дерево, то стягивающее дерево с минимальной стоимостью получается почти без дополнительных усилий. Очевидный метод получения какого-либо стягивающего дерева состоит в построении множества его ребер таким образом, чтобы на каждом шаге прибавлялось по одному ребру и проверялось, не образует ли добавленное ребро цикл с ребрами, уже включенными в множество. Какие изменения нужно внести в этот алгоритм для того, чтобы гарантировать получение минимального стягивающего дерева. Ответ на этот вопрос дает следующий алгоритм. [20]
Доказательства того, что эти два алгоритма действительно приводят к построению минимальных деревьев, нетрудны ( при использовании следующего доказанного выше факта: дерево, в котором нельзя сделать уменьшающую стоимость замену, является минимальным стягивающим деревом) и оставляются читателю в качестве упражнений. Какой из трех алгоритмов наиболее эффективен, зависит от способа задания графа. [21]
Наша задача состоит в разбиении множества ребер G на два таких класса, чтобы ребра, принадлежащие одному из классов, образовали стягивающее дерево, причем их общая стоимость была бы не больше стоимости любого другого стягивающего дерева. Предположим, что для начала у нас есть некоторое стягивающее дерево; наш алгоритм будет состоять в последовательности замен, при которых к этому дереву добавляется ребро, ранее ему не принадлежавшее, а некоторое ребро выбрасывается. [22]
Граф О может быть представлен своей матрицей основных циклов, которая определяется следующим образом. Выберем произвольное стягивающее дерево Т графа G. Каждое ребро е, не принадлежащее Т, определяет единственный цикл в Т, состоящий из самого ребра е и множества ребер, которое в разд. В матрице основных циклов F графа G ( соответствующей Т) каждому ребру С соответствует столбец, а каждому основному циклу - строка. Элемент Гц равен единице, если BJ принадлежит основному циклу с, и равен нулю в противоположном случае. [23]
Любой мой ход навсегда соединит две вершины графа и дает в результате граф, с точки зрения данной игры эквивалентный такому графу, в котором эти две вершины сливаются в одну. Более того, стягивающее дерево Т2, которое содержало ребро, исключенное в результате такого слияния, очевидно, остается стягивающим деревом нового графа. [24]
Один ( не очень существенный) недостаток изложенного алгоритма для построения минимального стягивающего дерева состоит в предположении, что с самого начала у нас уже есть по крайней мере одно стягивающее дерево. С другой стороны, если сначала нужно построить стягивающее дерево, то стягивающее дерево с минимальной стоимостью получается почти без дополнительных усилий. Очевидный метод получения какого-либо стягивающего дерева состоит в построении множества его ребер таким образом, чтобы на каждом шаге прибавлялось по одному ребру и проверялось, не образует ли добавленное ребро цикл с ребрами, уже включенными в множество. Какие изменения нужно внести в этот алгоритм для того, чтобы гарантировать получение минимального стягивающего дерева. Ответ на этот вопрос дает следующий алгоритм. [25]
Наша задача состоит в разбиении множества ребер G на два таких класса, чтобы ребра, принадлежащие одному из классов, образовали стягивающее дерево, причем их общая стоимость была бы не больше стоимости любого другого стягивающего дерева. Предположим, что для начала у нас есть некоторое стягивающее дерево; наш алгоритм будет состоять в последовательности замен, при которых к этому дереву добавляется ребро, ранее ему не принадлежавшее, а некоторое ребро выбрасывается. [26]
Один ( не очень существенный) недостаток изложенного алгоритма для построения минимального стягивающего дерева состоит в предположении, что с самого начала у нас уже есть по крайней мере одно стягивающее дерево. С другой стороны, если сначала нужно построить стягивающее дерево, то стягивающее дерево с минимальной стоимостью получается почти без дополнительных усилий. Очевидный метод получения какого-либо стягивающего дерева состоит в построении множества его ребер таким образом, чтобы на каждом шаге прибавлялось по одному ребру и проверялось, не образует ли добавленное ребро цикл с ребрами, уже включенными в множество. Какие изменения нужно внести в этот алгоритм для того, чтобы гарантировать получение минимального стягивающего дерева. Ответ на этот вопрос дает следующий алгоритм. [27]
Рассматриваемый алгоритм несколько необычен для комбинаторных алгоритмов: отталкиваясь от произвольно выбранного начального стягивающего дерева, он ведет прямо к стягивающему дереву минимальной стоимости. Когда окажется, что совершить очередную замену невозможно, имеется гарантия, что найдено стягивающее дерево минимальной стоимости. Так происходит потому, что в пространстве стягивающих деревьев отсутствуют локальные минимумы, из которых нужно было бы выбираться для достижения абсолютного минимума. [28]
Любой мой ход навсегда соединит две вершины графа и дает в результате граф, с точки зрения данной игры эквивалентный такому графу, в котором эти две вершины сливаются в одну. Более того, стягивающее дерево Т2, которое содержало ребро, исключенное в результате такого слияния, очевидно, остается стягивающим деревом нового графа. [29]
Пусть дано п точек на плоскости. Требуется найти кратчайший путь, соединяющий эти точки так, что из любой данной точки можно достичь любой другой точки, проходя через некоторые из точек, если это необходимо. Это может быть минимальное стягивающее дерево, если граф реально задан. [30]