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

- 60 - Будем считать расстоянием от вершины х j до изолированного фрагмента минимальное из расстояний от вершины х j до вершин данного фрагмента (рис. 24). Рис. 24 Неориентированное дерево есть: 1) связный граф, содержащий n вершин и n -1 ребер; 2) связный граф, не имеющий циклов; 3) граф, в котором каждой паре вершин инцидентна одна, и только одна простая цепь. Если G =( X,E ) – неориентированный граф с n вершинами (рис. 25, а ), то остовным деревом графа G (остовом) называется всякий остовный подграф графа G , являющийся деревом с n вершинами (рис. 25, б , в ). Такие деревья называются покрывающими. Рис. 25 Рис. 26