Алгоритм парных перестановок для решения задач оптимизации компоновки и размещения элементов РЭС: Учебное пособие, страница 29

Таблица 4.1

Матрица смежности

 

Минимизацию числа пересечений графа можно провести методом парных перестановок его вершин. Этот метод можно проиллюстрировать следующим образом: пусть граф, представленный на рис. 4.1, имеет пересечение ребер. Осуществим парную перестановку первой и четвертой вершин графа, в результате чего получим граф без пересечений (рис. 4.2).

Общее количество пересечений для графа с n вершинами можно определить по формуле

            (4.1)

где n – число вершин графа;

 

1, если между ребром (i,j) и ребром (k,l) есть

p[(i,j),(k,l)]=         пересечение

0, в противном случае;

m_ij, m_kl - элементы матрицы смежности.

В другой форме можно записать

             (4.2)

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

Пусть в некотором графе ребра, инцидентные вершине A, имеют следующее число пересечений с остальными ребрами графа:

.

Аналогично, для вершины B

.

После перестановки местами вершин A и B число пересечений изменится и станет равным:

.

.

Тогда изменение числа пересечений в результате перестановки вершин A и B выразится формулой :

.

Если  > 0, то перестановка вершин A и B целесообразна, так как ведет к уменьшению числа пересечений.

Определить наличие пересечений p[(i,j);(k,l)] между ребрами (i,j) и (k,l) можно следующим образом в соответствии с рис. 4.3, 4.4.

Ребра А₁А₂ и В₁В₂ являются отрезками прямых линий. Прямая линия описывается уравнением [8]:

y = kx + b.

Прямая, на которой лежит отрезок А₁А₂, описывается уравнением :

y = a₁x+b₁,  где .

Аналогично для В1В2:

y = a₂x+b₂,  где  .

Точка Z пересечения этих прямых имеет координаты :

 .

Необходимо далее определить, принадлежит ли точка Z(x*,y*) обоим отрезкам А₁А₂, В₁В₂ в соответствии с рис. 4.3.

 

Если точка Z принадлежит заштрихованной области, значит она принадлежит обоим отрезкам :

Z Î [A₁,A₂],   Z Î [B₁,B₂], следовательно является точкой пересечения отрезков (A₁,A₂), (В₁,В₂), т.е.

Z = (A₁,A₂) Ç (B₁,B₂).

Это значит, что x_min < x* < x_max, y_min < y* < y_max, для каждого отрезка, где х_min – большее значение из двух минимальных значений координаты х отрезков А₁А₂ и В₁В₂;

y_min – большее значение из двух минимальных значений координаты y отрезков А₁А₂ и В₁В₂;

х_max – меньшее значение из двух максимальных значений координат х отрезков А₁А₂ и В₁В₂;

y_max – меньшее значение из двух максимальных значений координат y отрезков А₁А₂ и В₁В₂.

Выполнение этого условия равноценно тому, что расстояние от обоих концов каждого отрезка до точки пересечения прямых меньше длины отрезка. Этот способ определения принадлежности точки пересечения отрезкам А₁А₂ и В₁В₂ был реализован в программе.

Кроме такого общего случая расположения прямых на плоскости относительно координатных осей, возможны частные случаи :

1. x_A1 = x_A2, x_B1 ¹ x_B2; (рис. 5.5)

Тогда x* =  x_A1; y* = a₂x*+b₂, где  .

2. x_B1 = x_B2, x_A1 ¹ x_A2;

Тогда x* =  x_B1; y* = a₁x*+b₁, где

3. y_A1 = y_A2, y_B1 ¹ y_B2

Тогда y* =  y_A1;

где .

4. y_В1 = y_В2, y_A1 ¹ y_A2

Тогда y* =  y_B1;

где .

5.     x_A1 = x_A2,

,     тогда   x* = x_A1, y* = y_B1

y_B1 = y_B2

6.     x_B1 = x_B2,

, тогда   x* = x_B1, y* = y_A1

y_A1 = y_A2

7.     x_A1 = x_A2,

x_B1 = x_B2 ,    тогда  пересечение отсутствует

x_A1 ¹ x_B1

8.     y_A1 = y_A2,

y_B1 = y_B2 ,    тогда  пересечение отсутствует

y_A1 ¹ y_B1

9.     к₁ = к₂,

,        тогда  пересечение отсутствует (рис. 4.6)

b₁ ¹ b₂

10.   x_A1 = x_A2,     тогда  оба отрезка находятся на