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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

15
минимальной степени в графе исключения G
k
, а перестановка строк и столб-
цов – это перенумерация вершин (т. е. k-я вершина становится j-той, а j-я – k-
той).
Здесь мы не забо тимся о том, что можем не получить устойчивость, т. к.
считается, что все активные матрицы хорошо обусловлены.
Недостатки:
1) полученное заполнение может оказаться хуже оптимального,
2) заранее мы не можем оценить требуемый объём памяти.
Задача 44.
Для графа G реализовать алгоритм минимальной степени и
нарисовать портрет полученной переупорядоченной матрицы.
№
вершин
1
→
1
2
→
2
3
→
6
→
8
→
9
4
→
5
→
10
5
→
4
6
→
3
7
→
9
→
8
8
→
6
9
→
7
10
→
5
1 1
0
3
8
7
4 2
9
6
5
1
G
1
≡
G
10 3 8
7 4 2 9
6 5
2
G
2
10 6 8
7 5
9
5
10
G
5
6 8
7 10
9
6
8
G
6
4
5
10 6 8
7 4
9
5
G
4
8
7 10
9
7
9
G
7
8
9 10
9
8
G
8
9
10
10
9
G
9
10 3 8
7 4
9
5
6
3
6
G
3 
                                                                           15

минимальной степени в графе исключения Gk, а перестановка строк и столб-
цов – это перенумерация вершин (т. е. k-я вершина становится j-той, а j-я – k-
той).
    Здесь мы не заботимся о том, что можем не получить устойчивость, т. к.
считается, что все активные матрицы хорошо обусловлены.

                                                                   Недостатки:
1) полученное заполнение может оказаться хуже оптимального,
2) заранее мы не можем оценить требуемый объём памяти.

Задача 44. Для графа G реализовать алгоритм минимальной степени и
    нарисовать портрет полученной переупорядоченной матрицы.
                                                                   1
№ вершин                                                       1                    10                  3                8
  1→ 1
  2→ 2                                     6                                                 G1≡G                                      5
  3→ 6→ 8→ 9
  4→ 5→ 10                                                     9                    2                   4                7
  5→ 4
  6→ 3                                                                              10                  3                8
  7→ 9→ 8                                                                                       G2
                                               6                                                                                       5
  8→ 6                                                                                   2
  9→ 7                                                         9                     2                  4                7
 10→ 5
                                       6
                                                                                    10                      6             8
              10                   3                       8
     6                                                                                                                    G4           5
                                           3
 3
                                           G                               5
                                                                                                                                           4
                                                                                     9                      4             7
                  9                4                       7                                            5
                                                                                                                 8
                                                                                                                                       6
                                                                                                                6                  8
             10                6                           8
                  5
                      5                                                                                              G6
                      G            10
                                                                                               9                10                 7
              9                5                           7
                                                                           9                                                  10

                          8                                            8                                                 9
                                                                                8                                             G9
                               7
                               G                                               G
         7                                                                                                           9
                                                       9                                            8
         9                10                       7                   10                      9                         10

Страницы