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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

28
6) Перенумеровываем вершины графа в соответствии со стратегией предыду-
щего пункта (роль параллельных сечений здесь играют УС).
Задача 50.
Реализовать МПС (1-й вариант) для графа G из задачи 46 и нари-
совать переупорядоченную матрицу (верхний треугольник с диагональ-
ными блоками).
1) v = 8 - периферийная вершина;
2) СУС для v = 8 построена в задаче 46: n = 6;
3) m = [20 / 6] = 3;
4) k =
[√
2
⋅
6/
√
9
]
=[2
√
2]=2;
5) p = 4 / 2 = 2; L
1
, L
3
, L
5
- разделители, т.е.
S
1
= L
1
= {9, 19, 3}, S
2
= L
2
= {17, 18, 11}, S
3
= L
3
= {13, 15, 5, 20};
R
1
= L
0
= {8}, R
2
= L
2
= {2, 10}, R
3
= L
4
= {12, 4, 14, 16, 1, 7}, R
4
= L
6
={6}.
*
* *
*
∗
R
1
R
2
R
3
R
4
S
1
S
2
S
3
*
*
*
S
3
2
0
51513111817319967116144121028
2
0
19181716151413121110987654321
R
1
R
2
R
3
R
4
S
1
S
2
20
5
15
13
11
18
17
3
19
9
6
7
1
16
14
4
12
10
2
8
15
7
3
1
20
19
18
17
16
14
13
12
11
10
9
8
6
5
4
2
* *
*
*
* *
*
*
*
*
*
∗
*
* *
* *
*
*
*
* *
*
*
*
*
* *
*
* *
*
*
*
*
*
*
*
*
*
*
* *
*
*
*
*
*
*
*
*
*
*
* *
* *
*
*
*
*
*
* * *
* *
* *
* *
* *
*
*
* 
                                             28

6) Перенумеровываем вершины графа в соответствии со стратегией предыду-
   щего пункта (роль параллельных сечений здесь играют УС).

Задача 50. Реализовать МПС (1-й вариант) для графа G из задачи 46 и нари-
     совать переупорядоченную матрицу (верхний треугольник с диагональ-
     ными блоками).

1) v = 8 - периферийная вершина;
2) СУС для v = 8 построена в задаче 46: n = 6;
3) m = [20 / 6] = 3;
4) k = [√2⋅6/√9]=[2√2]=2;
5) p = 4 / 2 = 2; L1, L3, L5 - разделители, т.е.
   S1 = L1 = {9, 19, 3}, S2 = L2 = {17, 18, 11}, S3 = L3 = {13, 15, 5, 20};
   R1 = L0 = {8}, R2 = L2 = {2, 10}, R3 = L4 = {12, 4, 14, 16, 1, 7}, R4 = L6 ={6}.

                    R1    R2     R3             R4     S1      S2            S3

                     1 2 3     4 5 6    7 8 9 10 11 12 13 14 15 16 17 18 19 20
                     8 2 10 12 4 14 16 1 7 6 9 19 3 17 18 11 13 15 5 20
     R1
          1    8 *                                    * * *
     R2
          2    2   * *                                *       * *
          3    10        * *                          * *       *   *
          4    12              **                             *
          5    4               * *                            * *
     R3   6    14
                                      * *                           *
          7    16                     * * *                         *
          8    1                        * * *                       *
          9    7                          * *                       *         * *
     R4 10     6                                  *                           * *
        11      9 * * *                               * *
     S1 12     19 *   *                               * **
          13   3 *                                      **
          14   17        *   **                               * ∗
     S2
          15   18        * *  *                               * * *
          16   11          *    * * * *                         * *
          17   13                                                       ∗*
     S3 18     15                                                       **
        19     5                           * *                                * *
          20   20                          * *                                * *

Страницы