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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

89
Вычислим константу приведения h:
∑∑
==
β+α=
5
1
5
1 j
j
i
i
h
= 24 + 6 = 30
и нижнюю границу γ(Z) множества Z(5):
hZ =γ )(
= 30.
По матрице
A
~
сформируем множество D:
}0
~
/),{( ==
kl
alkD
= {(1, 5), (2, 1), (2, 4), (3, 4), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4)}
и для каждого его элемента вычислим соответствующее значение
:
kl
α
′
5
1
1
5
15
~
min
~
min
r
r
r
r
aa
≠≠
+=α
′
= min {
11
~
a
,
12
~
a
,
13
~
a
,
14
~
a
} +
+ min {
25
~
a
,
35
~
a
,
45
~
a
,
55
~
a
} = min {∞, 22, 33, 9} +
+ min {2, 10, 0, ∞} = 9 + 0 = 9,
21
α
′
= min {∞, 10, 0, 2} + min {∞, 17, 17, 0} = 0 + 0 = 0,
24
α
′
= 0 + 0 = 0,
34
α
′
= 10 + 0 = 10,
45
α
′
= 3 + 0 = 3,
51
α
′
= 0 + 0 = 0,
52
α
′
= 0 + 3 = 3,
53
α
′
= 0 + 10 = 10,
54
α
′
= 0 + 0 = 0.
Далее определим
bc
α
′
:
kl
Dlk
bc
α
′
=α
′
∈),(
max
= max {9, 0, 0, 10, 3, 0, 3, 10, 0} = 10.
Заметим, что здесь
34
α
′
= 10 и
53
α
′
= 10, следовательно, в качестве
дуги ветвления (b, c) может быть выбрана дуга (3, 4) или дуга (5, 3). Вы-
берем для определённости первую из них.
Вычислим нижнюю границу множества
)1(
2
Z
:
bc
ZZ α
′
+γ=γ )()(
)1(
2
=
34
)( α
′
+γ Z
= 30 + 10 = 40.
Стянув матрицу
A
~
по выбранной дуге ветвления (3, 4) путём удале-
ния строки 3 и столбца 4, а также заменой значения элемента
43
~
a
на ∞,

Страницы