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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

9
***
***
****
****
***
***
******
****
***
***
***
5
4
3
7
8
2
11
9
10
6
1
1 2 3 4 5 6 7 8 9 10 11 новые номера строк
1 6 10 9 11 2 8 7 3 4 5 старые номера строк
§5. Алгоритм уменьшения профиля разреженной матрицы
Это так называемый обратный алгоритм Катхилл-Макки.Он состоит в
следующем.
1) Реализуем обычный алгоритм Катхилл-Макки.
2) Вершины полученного графа нумеруются в обратном порядке, то есть i-ой
вершине присваивается новый номер k = n + 1 – i (i = 1,..,n).
Теорема.
Обратный алгоритм Катхилл-Макки не увеличивает ширину ленты,
но может уменьшить ее профиль.
Задача 37.
Реализовать алгоритм уменьшения профиля разреженной матрицы
для графа G.
В результате при v
1
= 6 получили следующий граф:
10
11
9
8
6
7
5
1
2
4
3
1
6
10
2
11
4
8 5
7
3
9
L
1
L
0
L
2
L
2
L
3
L
3
L
4
L
5
L
4
L
5
L
4
9
11
8 10
7
5 4
6
3
1
2 
                                                            9

           1 2 3 4 5 6 7 8 9 10 11                                               новые номера строк
           1 6 10 9 11 2 8 7 3 4 5                                               старые номера строк
        1 *    *   *                                                        
                                                                            
        6 *    *       *                                                    
       10 *        *           *                                            
                                                                            
        9      *       *       *       *                                    
       11          *   *       *               *       *       *            
                                                                            
        2              *               *                           *        
                                                                            
        8                      *               *                           *
        7                      *                       *       *   *        
                                                                            
        3                      *                       *       *           *
        4                              *               *           *        
                                                                            
        5 
                                               *               *           *
                                                                             

       §5. Алгоритм уменьшения профиля разреженной матрицы
   Это так называемый обратный алгоритм Катхилл-Макки.Он состоит в
следующем.
1) Реализуем обычный алгоритм Катхилл-Макки.
2) Вершины полученного графа нумеруются в обратном порядке, то есть i-ой
   вершине присваивается новый номер k = n + 1 – i (i = 1,..,n).

Теорема. Обратный алгоритм Катхилл-Макки не увеличивает ширину ленты,
  но может уменьшить ее профиль.

Задача 37. Реализовать алгоритм уменьшения профиля разреженной матрицы
      для графа G.        L1     L2             L4        L5 11
                                                            3                         7
                                    1               10              L3           8             5
                            2                                               6                           L4
                                                                    11
                                                                                                        3
                                                                                                         9
                                    6               2                   9        4             7
                            1                               4               5         10            8
                                L0                  L2              L3           L5            L4
В результате при v1 = 6 получили следующий граф:
               10       9                                           5            1
                                            6
                                                                                           3

               11       8                   7                       2            4

Страницы