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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

8
1110987654321
=
******
***
****
***
****
***
***
***
****
***
***
11
10
9
8
7
6
5
4
3
2
1
A
3) Если СУС построена, то алгоритм закончен, и мы получили новую
нумерацию вершин (новый номер вершины – это номер строки, а номера
смежных с ней вершин – это номера столбцов).
Задача 35.
Реализовать алгоритм Катхилл-Макки для графа G.
v
1
=2;
L
0
: 2;
L
1
: 4;
L
2
: 6, 9, 7;
L
3
: 1, 3, 11;
L
4
: 5, 8, 10.
Задача 36.
Для матрицы А уменьшить ширину ленты, пользуясь алгоритмом
Катхилл-Макки (при перенумерации вершин мы задаём перестановку
строк и столбцов), и нарисовать переупорядоченную матрицу.
9
11
8
10
6
4
2
1 3
5
1
L
0
6
L
1
9
L
2
10
L
1
11
L
2
2
L
3
4
L
4
8
L
3
5
L
4
3
L
3
7
L
3
7
L
3
L
2
L
4
L
3
L
4
L
3
L
4
L
2
2
1
6
4
9
10
11
7
8
3
5
L
0
L
1
L
2
6
3
9
4
8
11
7
10
5
2
1 
                                                               8

3) Если СУС построена, то алгоритм закончен, и мы получили новую
   нумерацию вершин (новый номер вершины – это номер строки, а номера
   смежных с ней вершин – это номера столбцов).

Задача 35. Реализовать алгоритм Катхилл-Макки для графа G.
                6   L4            9                       11       L4
       L3       1         10                      8            8                  L4                v1=2;
                                                                                       10
                                  4       L3 11                                   5                 L0: 2;
         3          L2                                             7
                                                                                                    L1: 4;
       L2 6               9                               L3 3                                      L2: 6, 9, 7;
                                          L2 7                                                      L3: 1, 3, 11;
            1                                         5                                             L4: 5, 8, 10.
        L0 2              4
                    L1                2

Задача 36. Для матрицы А уменьшить ширину ленты, пользуясь алгоритмом
      Катхилл-Макки (при перенумерации вершин мы задаём перестановку
      строк и столбцов), и нарисовать переупорядоченную матрицу.

                            1              2 3 4 5 6                    7 8 9 10                 11
                         1 *                      *                          *                   
                                                                                                 
                         2                *   *                            *                     
                         3                  *   *                      *                       *
                                                                                                 
                         4                *   *                        *                         
                         5                 *   *                        *                       
                                                                                                  
                     A = 6 *                      *                        *                     
                                                                                                 
                         7                  * *                        *                       *
                         8                      *                        *                     *
                                                                                                 
                         9                *       *                        *                   *
                        10 *                                                 *                 *
                                                                                                 
                        11 
                                                *                      * * * *                 *

                         L0                  L1                     L2                 L3                L4
                     1                      10                     11                  8                5 11
                              1                   3                      5                  7

                                                                                                         L3
                         L1                  L2                                                         3     9
                     6                      9              L3                              L3
                     2                      4              2                           7
                                                                         L4                     8
                                                           6
                                                                        4
                                                                             10

Страницы