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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

24
1 шаг:
u=8 -периферийная вершина,
m=6 -длина структуры уровней
⇒
j=3; L
3
={11,17,18}
⇒
S={11}
⇒
11
→
20; C={11}, n=19.
2 шаг:
R
1
={12,4,17,18,2,10,9,19,8,3},
R
2
={13,15,14,16,1,7,5,20,6}.
R
1
: u=12, m=5
⇒
j=3;
S
1
=L
3
={9,10}
⇒
9
→
19,10
→
18.
R
2
: u=13, m=6
⇒
j=3;
S
2
=L
3
={1}, 1
→
17.
R
1
1
={12,4,17,18,2},
R
2
1
={19,8,3};
R
1
2
={13,15,14,16}, R
2
2
={7,5,20,6}.
………….
Дерево вложенных сечений:
Получим следующую переупорядоченную матрицу (т.к. матрица
симметрична, то изображен только верхний треугольник с диагональными
блоками):
11
9,10 1
17,4 19,8,3 5,20
7 6 13,15 2,18
14
16 12
S
0
S
1
1
S
1
2
S
2
4
S
2
1
S
3
1
S
3
6
S
2
2
S
2
3
S
3
2
S
3
3
S
3
4
S
3
5
4
17 18
12
10
2
9 19
14
8 3
11
20
15
16
13
7 5
10
6
L
4
L
3
L
2
L
4
L
5
L
4
L
5
L
4
L
4
L
3
L
2
L
3
L
6
L
4
L
0
L
1
L
1
L
4
L
5
L
5
                                                                        24


          L4              L5
L4 12            4              13              15
                                                     L5        1 шаг: u=8 -периферийная вершина,
                                                                      m=6 -длина структуры уровней ⇒
                          L4
           L3
                                                     L4
                                                                      j=3; L3={11,17,18}⇒ S={11}⇒
L3   17          18             14              16                         11→ 20; C={11}, n=19.
           L2              L3
L2   2           10             11              10 L4     2 шаг: R1={12,4,17,18,2,10,9,19,8,3},
                           L4
                                                                 R2={13,15,14,16,1,7,5,20,6}.
            L1
                                                     L5                   R1: u=12, m=5 ⇒ j=3;
L4   9           19             7               5                         S1=L3={9,10} ⇒ 9→ 19,10→ 18.
           L1              L5                                             R2: u=13, m=6 ⇒ j=3;
L0   8           3              20              6 L6                      S2=L3={1}, 1→ 17.
                                                                          R11={12,4,17,18,2},
          R21={19,8,3};
                                                                             R12={13,15,14,16}, R22={7,5,20,6}.

                                    .


                                                Дерево вложенных сечений:

                                                                    S0
                                                                      11
                                         S11                                              S12
                                          9,10                                       1
                          S21                                                                      S24
                                                                    2           3
                                                               S2          S2
                            17,4                      19,8,3                        14          5,20
                      1
                 S3                                                                                          S36
                      12                2,18              13,15                     16       7           6
                                          S32              S33                      S34     S35




  Получим следующую переупорядоченную матрицу (т.к. матрица
симметрична, то изображен только верхний треугольник с диагональными
блоками):

Страницы