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

- 74 - Назовем два отрезка соединения смежными, если они имеют общую точку (угловую или вершину Штейнера). Будем считать, что введение перехо- дов возможно лишь в общих точках отрезка. Рис. 44 1. В очередном дереве соединений выделяется множество Р непомеченных отрезков, каждый из которых является смежным по крайней мере для одного помеченного отрезка дерева. 2. Каждый отрезок p ∈ P поместить в тот же слой, к которому отнесен смежный с ним. Если же имеются смежные отрезки из разных слоев, то вы- брать тот отрезок, при назначении которого число переходов будет минималь- ным. Пометить его. 3. Выполнять первый и второй пункты до тех пор, пока в дереве все отрез- ки не будут помечены. 4. Ввести переходы во всех точках дерева, которые являются общими для отрезков, распределенных в разные слои. Проиллюстрируем работу алгоритма. Условимся изображать сплошной линией горизонтальные слои, пунктирной – вертикальные, ⊗ – точки Штейне- ра, × – угловые точки (рис.44, а ). Получили четыре угловые точки и одну точку Штейнера. В результате работы алгоритма получили две угловые точки и одну точку Штейнера (рис. 44, б ).