Методы решения систем с разреженными матрицами. Теория графов. Глушакова Т.Н - 22 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

22
R
1
R
2
R
1
1
R
1
2
R
2
1
R
2
2
v
1, …,
v
q-1
, v
q
, v
q+1, …,
v
k-1
, v
k, …,
v
p-1
, v
p
, v
p+1, …,
v
n-1
↓
↓
↓
↓
↓
↓
v
k-1,
v
q, …,
v
k-2
v
n-1 ,
v
p, …,
v
n-2
(k+1
→
k, k+2
→
k+1,…,n
→
n-1), то любая вершина из R
2
не будет достижима из
вершин R
1
:
v
j
∉
Reach(v
i
,Q
i
) (j=k,…,n; i
≤
k–1), что в соответствии с теоремой
Джорджа-Лю означает, что все такие элементы u
ij
в матрице заполнения U
равны нулю (рис.1).
Опр.
Выделение разделителя S называется сечением (так как он рассекает
граф на большее количество компонент).
С каждой из выделенных компонент R
1
и R
2
повторяем предыдущие
рассуждения: находим разделители S
1
={v
q
} в R
1
и S
2
={v
p
} в R
2
, обозначаем
через R
1
1
={v
1
,...,v
q-1
}, R
1
2
={v
q+1
,...,v
k-1
}, R
2
1
={v
k
,...,v
p-1
}, R
2
2
={v
p+1
,...v
n-1
} и
перенумеровываем вершины в R
1
2
и R
2
2
указанным выше способом:
Соответствующая матрица изображена на рис.2.
В процессе выполнения процедуры измельчения разбиения возникают
множества R, в которых нельзя найти разделитель. В случае появления такого R
в качестве соо тветствующего множества S берется само множество R и
нумеруются его вершины. Выполнение процедуры прекращается, если все
множества типа R исчерпаны.
На практике матрицу упорядочивают так, как показано на рис. 3. Вершины
каждого множества типа S нумеруются в обратном порядке (то есть в
направлении от n к 1), как только такое множество будет построено, в то время
как множества типа R остаются непронумерованными. Таким образом,
окончательная нумерация получается непосредственно после выполнения
алгоритма.
Заметим, что разделитель можно выбирать по -разному. Но для того, чтобы
процедура вложенных сечений была наиболее эффективной, нужно
придерживаться следующих правил:
R
1
R
2
S
Рис. 1
R
1
1
R
2
1
S
1
R
2
1
R
2
2
S
2
S
Рис. 2
0
0
0
0
R
1
1
R
2
1
S
1
R
2
1
R
2
2
S
2
S
Рис. 3 
                                                           22

(k+1→ k, k+2→ k+1, ,n→ n-1), то любая вершина из R2 не будет достижима из
вершин R1: vj∉Reach(vi,Qi) (j=k, ,n; i≤k–1), что в соответствии с теоремой
Джорджа-Лю означает, что все такие элементы uij в матрице заполнения U
равны нулю (рис.1).

                                              R 11                                     R11
                                                           0
    R1                                        R21     0                                R21
                                              S1                                       S1
                                              R21                      0               R21
    R2                                        R22                                      R22
                                              S2
                                                                  0                    S2
    S                                         S                                        S

            Рис. 1                                         Рис. 2                            Рис. 3

Опр. Выделение разделителя S называется сечением (так как он рассекает
 граф на большее количество компонент).

   С каждой из выделенных компонент R1 и R2 повторяем предыдущие
рассуждения: находим разделители S1 ={vq} в R1 и S2 ={vp} в R2, обозначаем
через R11={v1,...,vq-1}, R12={vq+1,...,vk-1}, R21={vk,...,vp-1}, R22={vp+1,...vn-1} и
перенумеровываем вершины в R12 и R22 указанным выше способом:
                                R1                                    R2

                      R11             R12                       R21             R22

                v1,   , vq-1,   vq, vq+1,   , vk-1,       vk,    , vp-1,vp, vp+1, , vn-1
                                 ↓ ↓          ↓                       ↓ ↓           ↓
                                vk-1, vq,    v
                                            , k-2                     vn-1 , vp, , vn-2

   Соответствующая матрица изображена на рис.2.
   В процессе выполнения процедуры измельчения разбиения возникают
множества R, в которых нельзя найти разделитель. В случае появления такого R
в качестве соответствующего множества S берется само множество R и
нумеруются его вершины. Выполнение процедуры прекращается, если все
множества типа R исчерпаны.
   На практике матрицу упорядочивают так, как показано на рис. 3. Вершины
каждого множества типа S нумеруются в обратном порядке (то есть в
направлении от n к 1), как только такое множество будет построено, в то время
как множества типа R остаются непронумерованными. Таким образом,
окончательная нумерация получается непосредственно после выполнения
алгоритма.
   Заметим, что разделитель можно выбирать по-разному. Но для того, чтобы
процедура вложенных сечений была наиболее эффективной, нужно
придерживаться следующих правил:

Страницы