Информационные технологии проектирования электронных средств

- 62 - Дерево Т 1 =( Х 1 , Е 1 ) является поддеревом дерева Т =( Х , Е ), если Х 1 ⊆ Х , Е 1 ⊆ Е , причём поддерево может состоять и из одной вершины. Рассмотрим алгоритм: 1) выбираем вершину х 1 . Ee cчитаем поддеревом Т : Х 1 ={ х 1 }, Е 1 = ∅ ; 2) строим упорядоченный список Г ребер, инцидентных вершине х 1 , по возрастанию веса ребер; 3) из списка Г выбираем ребро с наименьшим весом. Пусть это ( х 1 , х 2 ). Таким образом, поддерево Т 1 разрастается; 4) в список Г вносим ребра, инцидентные вершине х 2 , и упорядочива- ем их по возрастанию веса, включая и уже находящиеся ранее в списке ребра; 5) из списка выбираем ребро с наименьшим весом, пусть это ( х 2 , х 4 ). Добавляем его к поддереву Т 1 в том случае, если оно не образует цикла с уже находящимися в поддереве ребрами. Остальные ребра, объединяющие верши- ны Х 1 между собой, исключаются из списка Г; 6) проверяем условие Х Х = 1 . Если оно выполняется, то осуществля- ется переход на конец алгоритма. В противном случае выбирается вершина х 3 из Х 1 и ребра, инцидентные ей, добавляются к списку Г. Переход к п. 4. 7) конец работы алгоритма. Задача Штейнера Пусть требуется найти наикратчайшее дерево Т , которое покрывает за- данное подмножество Р ⊂ Х вершин графа G ( X , E ). Другие вершины, принадле- жащие подмножеству Х \ Р, могут либо стягиваться деревом Т , либо нет, в за- висимости от требования минимума суммарной длины ребер дерева Т . Таким образом, задача Штейнера на графе эквивалентна нахождению наикратчайшего остовного дерева произвольного подграфа G ′ ( X ′ , E ) графа G ( Х , E ) при условии, что P ⊆ X ′⊆ X .