Исходные данные:
задан граф G=(X,U) в виде матрицы смежности (рис. 1)
рис. 1. Матрица R.
Задача: Разместить элементы в линейку с заданным критерием оптимальности.
Критерий оптимальности: минимум общей суммарной длины соединений между размещаемыми элементами.
В САПР часто графы представляют в виде координатной решетки. На прямоугольную конструкцию (ячейка, кристалл, панель) накладывается, декартова система координат с осями S, t , определяющая граф Gr, представляющий собой координатную решетку.
Задача размещения сводится теперь к отображению заданного графа G=(X,U) в решетку Gr=(Xr,Ur).
1 шаг.Разместить элементы произвольным образом в узлах решетки.
t
2
S
0 1 2 3
рис.2. граф Gr.
Хr - множество вершин размещается в узлах решеток.
Ur - множество ребер соответствует горизонтальным и вертикальным отрезкам, соединяющим узлы решетки.
Расстояние между смежными вершинами называется шагом решетки. В нашем случае шаг решетки принимается равным 1.
2 шагНеобходимо определить расстояние между двумя произвольными вершинами.
Расстоянием d(xi,xj) между вершинами Xi и Xj графа Gr=(Xr,Ur) называется длина кратчайшей цепи, соединяющей эти вершины.
