Под длиной цепи подразумевается число входящих в нее ребер.

Функцию расстояний для графа удобно задавать матрицей расстояний

D=//d_ij//n*n.

Расстояние между двумя произвольными вершинами можно определить по формуле:

d_ij = / S_i - S_j / + / t_i - t_j / (ф.1).

S_ij; t_ij - координаты вершин Xi,XjєXr.

Обычно задаются размеры решетки p*q (p - количество узлов решетки по оси S; q - количество узлов решетки по оси t.)

Например:

d_1,9 = /S₁-S₉/ + /t₁-t₉/ = /0-2/ + /0-2/ = 4

d_1,8 = /S₁-S₈/ + /t₁-t₈/ = /0-1/ + /0-2/ = 3

и.т.д.

В результате расчетов получаем матрицу D (рис.3)

рис. 3.Матрица D.

3 ШагСоставляем матрицу геометрий Dγ.

Матрица геометрий Dγ - это матрица смежности R, отображенная на координатную решетку. Элементы Dγ получаются путем поэлементного перемножения:

d^γ_ij=r_ij×d_ij

В результате получаем Dγ (рис. 4)

рис. 4 рис.5

4 шаг По матрице геометрии определяем суммарное значение связей каждого элемента с остальными Σd_ij.

Например: для элемента Xl суммарное значение связей

X1= d_1,3+d_1,2+d_1,4+d_1,5+d_1,6+d_1,7+d_1,8+d_1,9 = 3.

для элемента

X6 = d_6,1(3)+d_6,2(2)+d_6.3(0)+d_6,4(2)+d_6,5(l)+d_6,7(0)+d_6,8(0)+d_6,9(0) = 8

и т. д.

(рис.5)

Из полученного ряда значений выбирается элемент с минимальным значением связей X1 и устанавливается на первое посадочное место Р1 в линейке (рис.6)

5шагПреобразуем матрицу Dγ, исключив первую строку, а элементы первого столбца вычитаются из предыдущего суммарного значения связей Σdij.

В результате получаем следующее суммарное значение связей каждого элемента с учетом предыдущих преобразований над матрицей Dγ.

Например: для Х6 Σd_ij = Σd_ij(8) - d_6,1(3) = 5

Х2 Σd_ij = Σd_ij(11) - d_2,1(0) = 11

и.т.д.

Из полученного ряда значений выбираем элемент с min Σd_ij и устанавливаем на 2-ое посадочное место Р2. Это элемент Х5. (рис 6.)

6 шагДалее преобразуется матрица Dγ, исключив элемент Х5 (аналогично шагу 5).

На третьем месте закрепляется элемент Х7, т.к. Σd_ij на данном шаге для X7 - min и равен 3.

Далее вычисление ведется аналогично шагам 5, 6 до размещения всех элементов.

Окончательное размещение в линейку будет следующим:

рис.6.