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

- 61 - Ориентированное дерево представляет собой ориентированный граф без циклов, в котором полустепень захода каждой вершины, за исключением од- ной, например х 1 , равна единице, а полустепень захода этой вершины х 1 равна нулю. Тогда х 1 − корень дерева (рис.26). Рис. 27 Рассмотрим взвешенный связный неориентированный граф G =( X,E ) (рис. 27, а ). Из большого числа остовов графа нужно найти один, у которого сумма весов ребер будет минимальной ∑ → i,j ij C min . Такая задача возникает в том случае, когда вершины графа являются клеммами электрической цепи, которые должны быть соединены между собой проводами с наименьшей общей длиной. Это делается для уменьшения уровня наводок. Отметим, что дерево, дающее все кратчайшие пути, выходящие из неко- торой вершины (рис. 27, б ) , не всегда совпадает с кратчайшим остовом графа (рис. 27, в ) − кратчайшим покрывающим деревом (КПД). Алгоритм Прима построения КПД Алгоритм Прима построения КПД основывается на идее разрастания поддеревьев.