Составители:
86
один столбец или одна строка матрицы
[]
()
m
m
nL
+
R
, используемые для
вычисления элементов
()()
11
,
mm
ik kj
c
c
++
матрицы
[]
()
1
m
m
nL
+
+
C
, соответству-
ющих вновь введенным элементам
() ()
,
mm
ik kj
rr
, содержат только одну
единицу).
Поскольку элемент
()
m
ij
r
в матрице
[]
()
m
m
nL
+
R
, для которого введены
элементы
() ()
,
mm
ik kj
rr
, на m-й итерации становится равным нулю и оста-
ется таковым на всех последующих итерациях, то соответствующий
элемент
()
1
m
ij
c
+
матрицы
[]
()
1
m
m
nL
+
+
C
также оказывается равным нулю и
остается таковым до конца выполнения первого этапа. Следовательно,
на каждой итерации хотя бы один элемент
()
1
m
ij
c
+
матрицы
[]
()
1
m
m
nL
+
+
C
,
для которого соответствующий элемент r
ij
матрицы смежности R
[n]
не
равен нулю, становится равным нулю. При этом количество ненуле-
вых элементов в матрице
[]
()
1
m
m
nL
−
+
C
за счет введения в матрицу смеж-
ности R
[n]
дополнительных элементов в процессе выполнения итераций
не увеличивается.
Число элементов
0
ij
r ≠
в матрице R
[n]
конечно и равно L, а за каж-
дую итерацию размерность матрицы
[]
()
m
m
nL
+
R
увеличивается на конеч-
ное число, равное числу элементов
()
1
0
m
ij
r
−
≠
в матрице
[]
()
1
1
m
m
nL
−
−
+
R
, для
которых соответствующие элементы
()
m
ij
c
матрицы
[]
()
1
m
m
nL
−
+
C
не равны
нулю, поэтому, во-первых, число итераций в процессе построения мат-
рицы R
q
будет конечным, и, во-вторых, число добавленных столбцов, а
следовательно, и строк в матрице удовлетворяет неравенству
.
q
LL
≤
Страницы
- « первая
- ‹ предыдущая
- …
- 84
- 85
- 86
- 87
- 88
- …
- следующая ›
- последняя »
