ВУЗ:
Составители:
Рубрика:
,)(
∑
∑
∈∈
−=∆
pq
Jk
ik
Jk
ikiqp
SSvS
∑
∑
∈∈
−=∆
qp
Jk
jk
Jk
jkjpq
SSvS )( ,
где ∆S
qp
(v
i
), ∆S
qp
(v
j
) – числа связности вершин v
i
и v
j
; J
p
, J
q
– множества номеров вершин частей V
p
и V
q
соответственно.
Величина ∆S
qp
(v
j
) характеризует разность числа связей вершины v
i
∈ V
p
с вершинами v
j
∈ V
q
и с вершинами V
p
/ v
j
.
Расчет ∆
R(v
i
, v
j
) рекомендуется проводить в следующей последовательности. Сначала определяется матрица ∆R
1
пере-
становочных коэффициентов для вершин первой части, имеющая размерность N
1
× (m – N
1
). Для нашего примера эта матри-
ца имеет вид
,
где, в частности,
(
)
{ } {} {} { }
,1010002
2)()(,/,
13
5,4,3
3
2,1
3
2,1
1
5,4,3
1
1331212123113113
−=−−+−=−−+−=
=−∆+∆=∈∈∆=
∑∑∑∑
∈∈∈∈
SSSSS
SvSvSVvVvvvRr
k
k
k
k
k
k
k
k
()
{ } {} {} { }
.2001012
2)()(,/,
26
8,7,6
6
2,1
6
2,1
2
8,7,6
2
2661323136126226
=−−+−=−−+−=
=−∆+∆=∈∈∆=
∑∑∑∑
∈∈∈∈
SSSSS
SvSvSVvVvvvRr
k
k
k
k
k
k
k
k
Аналогично рассмотренным по формуле (1) вычисляются и остальные коэффициенты матрицы.
Затем определяются пары вершин, имеющих положительный знак ∆R. В рассматриваемом примере таковыми являются
{v
1
, v
4
}, {v
1
, v
8
} и {v
2
, v
6
}. Для пары вершин {v
2
, v
6
} значение ∆R максимально, поэтому в матрице смежности вершины v
2
и v
6
меняются местами.
Перестроенная матрица смежности имеет вид
Как видно из рис. 2, после первой итерации число внешних связей уменьшилось на две: с Q
0
= 7 до Q
1
= 5.
В случае отсутствия положительных компонентов матрицы ∆R
1
строится матрица ∆R
2
размерностью N
2
× (m – (N
1
+
N
2
)), по которой определяется возможность перестановки вершин v
i
с вершинами
21
/ VVVv ∪
∈
. Если матрица ∆R
2
не содер-
жит положительных компонентов, то переходят к рассмотрению ∆R
3
и т.д. Решение задачи заканчивается, когда все компо-
ненты матрицы ∆R
n – 1
отрицательны или равны нулю.
На второй итерации с использованием формулы (1) заполняется матрица коэффициентов
1
R
′
∆ , т.е.
Страницы
- « первая
- ‹ предыдущая
- …
- 8
- 9
- 10
- 11
- 12
- …
- следующая ›
- последняя »
