Алгоритмы и модели трассировки

В зависимости от конструктивной реализации связей выделяют трассировку проводных соединений, трассировку печатных соединений трассировку на кристалле БИС.

Среди всех конструктивно - технологических реализаций связей проводной монтаж с точки зрения практического решения задачи трассировки наиболее прост. Это объясняется тем, что проводники изолированы друг от друга и не стоит задачи об ограничениях на пересечениях. Поэтому основным критерием трассировки проводных соединений является суммарная длина соединений.

Для проводного монтажа задача трассировки сводится к построению на вершинах графа дерева с минимальной суммарной длиной ребер, при этом вершины моделируют соединяемые контакты, а ребра - межсоединения. Единственное ограничение накладывается на максимальную локальную степень вершины, т.к. технологически целесообразно подсоединять к одному контакту не более определенного конечного числа соединений.

Задача построения минимального дерева, т.е. определение КПД. Решение задачи дано в работах Краскала, Лобермана, Уйэнберга и Прима.

Связаный граф без циклов называется деревом и обозначается:

T = (X, U) |X| = n

Любое дерево Т имеет (n-1) ребро.

Начальная вершина называется корнем, из которого выходят ребра - ветви дерева.

В дереве любые две вершины Xi, Xj связаны единственной целью.

В любом связном графе G можно выделить произвольное дерево Т.

Наибольший интерес в конструкторском и технологическом проектировании представляют деревья, у которых число вершин равно числу вершин графа, из которого выделено это дерево.

Такие деревья называются покрывающими или основными.

Число покрывающих деревьев t в полном графе Kn составляет t=nⁿ^-2.

Рис. 8.8 Рис. 8.9

t_l=n^3-2=3 t₂=4^4-2=16

Полным графом называется граф, в котором между любой парой вершин имеется ребро ( обозн. Kn) t = nⁿ^-2; t₁= 3^3-2= 3; t₂= 4^4-2= 4²= 16 Множество деревьев графа называются лесом.

Часто в проектировании схем ставится задача нахождения оптимального соединения определенных точек (схем). В теории графов эта задача формулируется следующим образом: в связаном графе G = (X, U) отыскать маршрут, который начинается в заданной вершине Xi є X и приводит в искомую вершину Xj є X, причем маршрут должен содержать кратчайшее число ребер.

Задача состоит в определении одного из n-2 возможных деревьев с минимизацией числа проводов.

ПРИМЕЧАНИЕ:

Каждому ребру Ui є U графа G = (X, U) ставится в соответствие некоторое неотрицательное число ν (U), называемое его мерой или весом (характеристика расстояния или важности связи).

Необходимо найти алгоритм построения минимального покрывающего дерева Т, у которого сумма мер, взятая по всем ребрам

Такие деревья называются кратчайшими покрывающими деревьями (КПД).

Графы с весами на ребрах или вершинах будем называть взвешенными.