Дискретная математика. Громов Ю.Ю - 86 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

86
где α
i
(i = 1, 2, …, n) − минимальный элемент i-й строки матрицы А;
β
j
( j = 1, 2, …, n) − минимальный элемент j-го столбца А′. Величину
β+α
∑∑
==
n
j
j
n
i
i
11
назовём константой приведения и обозначим через h:
∑∑
==
β+α=
n
j
j
n
i
i
h
11
.
Элементы матрицы
A
~
являются неотрицательными величинами.
Поэтому длина σ(π) любого контура π
∈
Z(n), вычисленная по матри-
це
A
~
, также будет неотрицательной величиной и, следовательно, длина
оптимального контура
0)
~
(
0
≥σ A
. Из этого факта и двух предыдущих
уравнений следует справедливость соотношения
hA
≥σ
)(
0
, т.е. констан-
та приведения является нижней границей γ(Z) множества Z(n):
hZ
=γ
)(
.
Приведённая матрица
A
~
содержит в каждой строке и каждом
столбце не менее одного нулевого элемента. Обозначим через D множе-
ство дуг, отвечающих нулевым элементам матрицы
A
~
:
}0
~
/),{(
==
kl
alkD
.
Для организации первого ветвления выберем дугу ветвления (b, c),
которая определяется максимальной величиной:
kl
Dlk
bc
α
′
=α
′
∈),(
max
,
где
rl
kr
kr
lr
kl
aa
~
min
~
min
≠≠
+=α
′
.
Нижняя граница множества
)1(
)1(
2
−nZ
вычисляется путём увеличе-
ния нижней границы его непосредственного предшественника Z(n) на
bc
α
′
:
bc
ZZ α
′
+γ=γ )()(
)1(
2
.
Далее в результате стягивания матрицы
A
~
по выбранной дуге ветв-
ления (b, c) получается матрица А
1
порядка (n − 1), соответствующая
множеству
)1(
)1(
1
−nZ
. При этом стягивание матрицы
A
~
заключается в
том, что из неё исключается строка b и столбец c, а элемент
cb
a
~
полага-

Страницы