Cтраница 3
Один ( не очень существенный) недостаток изложенного алгоритма для построения минимального стягивающего дерева состоит в предположении, что с самого начала у нас уже есть по крайней мере одно стягивающее дерево. С другой стороны, если сначала нужно построить стягивающее дерево, то стягивающее дерево с минимальной стоимостью получается почти без дополнительных усилий. Очевидный метод получения какого-либо стягивающего дерева состоит в построении множества его ребер таким образом, чтобы на каждом шаге прибавлялось по одному ребру и проверялось, не образует ли добавленное ребро цикл с ребрами, уже включенными в множество. Какие изменения нужно внести в этот алгоритм для того, чтобы гарантировать получение минимального стягивающего дерева. Ответ на этот вопрос дает следующий алгоритм. [31]
Очевидно, что стоимость окончательного дерева Т, полученного по такому алгоритму, не превышает стоимости любого из промежуточных деревьев, получаемых в процессе работы алгоритма. Действительно, из всех стягивающих деревьев Т обладает минимальной стоимостью. В частности, независимо от того, какое стягивающее дерево было взято за начальное, все деревья, построенные по такому алгоритму, будут иметь одинаковую стоимость. [32]
Циклом, ( замкнутым путем) называется такой путь ( в определенном выше смысле), у которого совпадают первая и последняя вершины. Дерево - это произвольный граф без циклов. G нельзя добавить ни одного ребра из G, не получив цикла), называется максимальным или стягивающим деревом G. Стягивающее дерево Т графа G обладает следующими свойствами. [33]
Циклом, ( замкнутым путем) называется такой путь ( в определенном выше смысле), у которого совпадают первая и последняя вершины. Дерево - это произвольный граф без циклов. G нельзя добавить ни одного ребра из G, не получив цикла), называется максимальным или стягивающим деревом G. Стягивающее дерево Т графа G обладает следующими свойствами. [34]
Один ( не очень существенный) недостаток изложенного алгоритма для построения минимального стягивающего дерева состоит в предположении, что с самого начала у нас уже есть по крайней мере одно стягивающее дерево. С другой стороны, если сначала нужно построить стягивающее дерево, то стягивающее дерево с минимальной стоимостью получается почти без дополнительных усилий. Очевидный метод получения какого-либо стягивающего дерева состоит в построении множества его ребер таким образом, чтобы на каждом шаге прибавлялось по одному ребру и проверялось, не образует ли добавленное ребро цикл с ребрами, уже включенными в множество. Какие изменения нужно внести в этот алгоритм для того, чтобы гарантировать получение минимального стягивающего дерева. Ответ на этот вопрос дает следующий алгоритм. [35]
На рис. 2.11 показано, как при помощи этого алгоритма находятся все три стягивающих дерева полного графа с тремя вершинами. Процедура заканчивается, когда граф распадается на две компоненты или превращается в единственную вершину. G, полученный слиянием вершин. Заметим, что информация о том, какие вершины были слиты, должна сохраняться для того, чтобы по стягивающему дереву было можно восстановить исходный граф. [36]
Простая цепь ( путь) в ненаправленном ( направленном) графе представляет собой последовательность ребер ( дуг) и вершин, в которой не повторяется ни одна вершина; контур ( цикл) представляет собой цепь ( путь), начальная и конечная вершины которого совпадают. Говорят, что граф является связным без учета направленности, если существует простая цепь между любой парой вершин. Граф с ( п 1) вершинами является п-кратно связным, если удаление ( п - 1) или меньшего числа вершин не делает его несвязным. Говорят, что две цепи не пересекаются, если они не имеют общих вершин, за исключением конечных точек. Дерево представляет собой связный подграф, в котором отсутствуют контуры. Стягивающее дерево ( остов) представляет собой ( максимальное) дерево, которое содержит все вершины графа. Ребро графа, которое входит в дерево, называется ветвью. Ребро графа, которое не входит в дерево, называется хордой. Дерево начинается в у, откуда исходят все пути дерева. [37]
Для доказательства того, что алгоритм 2.3 корректно строит стягивающее дерево произвольного связного графа, достаточно отметить следующие три факта. Таким образом алгоритм строит связный граф. Отсюда следует, что построенный граф F, Ту не содержит циклов. Действительно, последняя ветвь, замыкающая цикл, должна была бы соединить две уже рассмотренные вершины. И наконец, в-третьих, из свойства поиска в глубину следует, что процедура WGD просматривает все вершины связного графа. Следовательно, граф F, Г, построенный нашим алгоритмом, есть стягивающее дерево графа G. Вычислительная сложность алгоритма есть, очевидно, O ( n m), а:, е, того же порядка, что и поиск в глубину. [38]