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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

17
1
8
9
4
7
5
2
6
3
Задача 45
.
Для графа G реализовать алгоритм оценки объёма заполнения
в методе минимальной степени.
k=1: v
1
=1, deg U= deg1 =1.
k=2: 3) Reach(2,Q
2
)={3,5,7};
Reach(3,Q
3
)= {5,7}, deg U= 3;
Reach(5,Q
3
)={3,7,9},deg U= 6;
Reach(7,Q
3
)={3,5,4},deg U= 9.
k=3: Reach (3,Q
3
) = {5,7}; Reach (5,Q
4
) = {7,9}, deg U=11 ;
Reach (7,Q
4
) = {4,5}, deg U=13.
k=4: Reach(4,Q
4
) = {7,9}; Reach (7,Q
5
) = {5,9}, deg U=15;
Reach (9,Q
5
) = {5,6,7,8}, deg U=19.
k=5: Reach (5,Q
5
) = {7,9}; Reach (7,Q
6
) = {9}, deg U=20 ;
Reach (9,Q
6
) = {6,7,8}, deg U=23.
k=6: Reach (6,Q
6
) = {9}; Reach (9,Q
7
) = {7,8}, deg U=25.
k=7: Reach (7,Q
7
) = {9}; Reach (9,Q
8
) ={8}, deg U=26 .
k=8: Reach(8,Q
8
) ={9}; Reach (9,Q
9
) =
∅
, deg U=26.
Таким образом,
V
=26/2=13.
§10. Древовидное разбиение симметричной матрицы
(метод фактор-деревьев)
Если граф симметричной матрицы является деревом, то заполнения в
процессе гауссова исключения не происходит.
10.1. Определение фактор-дерева
Если вершины графа G объединить некоторым образом в группы
Г
1
,
Г
2
,…,Г
S
и ввести отношения эквивалентности, полагая v
i
~ v
j
тогда и только
тогда, когда v
i,
v
j
∈
Г
К
(одной группе), то множество вершин графа разбивается
на классы эквивалентности
.
Опр.
Фактор-графом
Φ
графа G называется граф, вершинами которого
являются вершины Г
1
, Г
2
,…, Г
S
, причем ребро (Г
К
, Г
Р
) принадлежит фактор- 
                                      17

Задача 45. Для графа G реализовать алгоритм оценки объёма заполнения
      в методе минимальной степени.

    1     8       9                        k=1: v1=1, deg U= deg1 =1.
                                           k=2: 3) Reach(2,Q 2)={3,5,7};
    6                                            Reach(3,Q3)= {5,7}, deg U= 3;
           5      4
                                                  Reach(5,Q3)={3,7,9},deg U= 6;
                                                  Reach(7,Q3)={3,5,4},deg U= 9.
   3      2       7

k=3: Reach (3,Q3) = {5,7}; Reach (5,Q4) = {7,9}, deg U=11 ;
     Reach (7,Q4) = {4,5}, deg U=13.

k=4: Reach(4,Q4) = {7,9}; Reach (7,Q5) = {5,9}, deg U=15;
     Reach (9,Q5) = {5,6,7,8}, deg U=19.

k=5: Reach (5,Q5) = {7,9}; Reach (7,Q6) = {9}, deg U=20 ;
     Reach (9,Q6) = {6,7,8}, deg U=23.

k=6: Reach (6,Q6) = {9}; Reach (9,Q7) = {7,8}, deg U=25.

k=7: Reach (7,Q7) = {9}; Reach (9,Q8) ={8}, deg U=26 .

k=8: Reach(8,Q8) ={9}; Reach (9,Q9) =∅, deg U=26.

    Таким образом, V=26/2=13.


              §10. Древовидное разбиение симметричной матрицы
                         (метод фактор-деревьев)

  Если граф симметричной матрицы является деревом, то заполнения в
процессе гауссова исключения не происходит.

                      10.1. Определение фактор-дерева

     Если вершины графа G объединить некоторым образом в группы
 Г1, Г2, ,ГS и ввести отношения эквивалентности, полагая vi ~ vj тогда и только
тогда, когда vi, vj ∈ГК (одной группе), то множество вершин графа разбивается
на классы эквивалентности.

Опр. Фактор-графом Φ графа G называется граф, вершинами которого
  являются вершины Г1, Г2, , ГS, причем ребро (ГК , ГР) принадлежит фактор-

Страницы