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

- 65 - 2. Анализируются все ребра, инцидентные этой вершине р i , и выбираются такие их реализации, которые дают максимальное совмещение путей с учетом ранее построенных соединений. 3. Повторяются первый и второй пункты до тех пор, пока для всех ребер дерева Т не будут получены однозначные реализации. Пример. Пусть имеется следующее расположение точек на плоскости (рис. 29, а ). Рассмотрим работу первого алгоритма построения дерева Штейнера. Со- единив фрагменты 1-1, 3-3, 4-4, получим три точки Штейнера, отмеченные × (рис. 29, б ). Построим для точек (рис. 36, а ) дерево Прима (рис. 29, в ). После соедине- ния точек L = { 1,2,5,4,6,8,3,7 } получим дерево Штейнера (рис. 29, г ). Рис. 29