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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

18
i
m
i
i
m
i
i
mmmN
∑
∑∑
∑∑
∑∑
∑
=
==
=
−
−−
−
=
==
=
+
++
+≤
≤≤
≤
1
1
0
2
графу Ф в том и только том случае, когда какие-либо две вершины из Г
К
, Г
Р
оказываются смежными.
Опр.
Если фактор-граф представляет собой дерево, то его называют фактор-
деревом, а соответствующее разбиение – древовидным разбиением. В этом
случае заполнения на блочном уровне не будет.
Переход к фактор-дереву иногда называют построением древовидной
структуры графа.
На матричном языке построение фактор-графа означает, что матрица А
разбивается на блоки. Например, пусть Г
К
= {v
к1
,v
к2
,…,v
кg
}, тогда Г
К
отвечает
блок на главной диагонали, получающейся в пересечении строк и столбцов с
номерами к1
,
к2,…,кg
.
Таким образом, происходит разбиение на блоки: каждой
группе Г
К
отвечает блок, стоящий на главной диагонали, порядок которого
равен числу вершин.
10.2. Простейшая древовидная структура
Простейшая древовидная структура – СУС L
0
, L
1
,…, L
m
.
Действительно, отождествим все вершины исходного графа G, относящиеся
к одному уровню L
i.
Легко убедиться, что полученный фактор-граф будет
деревом, которому соответствует блочно – 3-диагональное разбиение матрицы:
каждой вершине L
i
фактор-дерева отвечает блок (m
i
x m
i
) на главной диагонали
(где m
i
- количество вершин уровня L
i
), а вершина L
i
смежна с L
i-1
и L
i+1
(i=1,…,m-1). Поэтому фактор-графу будут принадлежать ребра (L
i-1
, L
i
), (L
i
,
L
i+1
), инцидентные с вершиной L
i
, а в матрице, соответствующей фактор-
дереву, будут отличны от нуля элементы l
i,i-1
, l
i,i+1
(а также l
i,i
).
Осуществив такое разбиение, можно найти объем заполнения N, который
оценивается суммированием всех порядков блоков полученных матриц:
Из (1) видно, что чем мельче древовидное разбиение (чем больше вершин в
фактор-графе), тем меньше объем возникающего заполнения, поэтому после
построения грубого древовидного разбиения целесообразно измельчить его.
(
1
)
.
0
)(
∑
∑∑
∑
=
==
=
=
==
=
m
i
i
nm
                                          18

графу Ф в том и только том случае, когда какие-либо две вершины из ГК , ГР
оказываются смежными.
Опр. Если фактор-граф представляет собой дерево, то его называют фактор-
  деревом, а соответствующее разбиение – древовидным разбиением. В этом
  случае заполнения на блочном уровне не будет.

    Переход к фактор-дереву иногда называют построением древовидной
структуры графа.

    На матричном языке построение фактор-графа означает, что матрица А
разбивается на блоки. Например, пусть ГК = {vк1,vк2, ,vкg}, тогда ГК отвечает
блок на главной диагонали, получающейся в пересечении строк и столбцов с
номерами к1, к2, ,кg. Таким образом, происходит разбиение на блоки: каждой
группе ГК отвечает блок, стоящий на главной диагонали, порядок которого
равен числу вершин.


                 10.2. Простейшая древовидная структура

   Простейшая древовидная структура – СУС L0, L1, , Lm.
   Действительно, отождествим все вершины исходного графа G, относящиеся
к одному уровню Li. Легко убедиться, что полученный фактор-граф будет
деревом, которому соответствует блочно – 3-диагональное разбиение матрицы:
каждой вершине Li фактор-дерева отвечает блок (mi x mi) на главной диагонали
(где mi - количество вершин уровня Li), а вершина Li смежна с Li-1 и Li+1
(i=1, ,m-1). Поэтому фактор-графу будут принадлежать ребра (Li-1, Li), (Li,
Li+1), инцидентные с вершиной Li, а в матрице, соответствующей фактор-
дереву, будут отличны от нуля элементы li,i-1, li,i+1 (а также li,i).




    Осуществив такое разбиение, можно найти объем заполнения N, который
оценивается суммированием всех порядков блоков полученных матриц:
                m            m                  m
           N ≤∑       mi2   +∑ mi −1 mi        ( ∑ m i =n ) .          (1)
               i =0          i =1               i =0


    Из (1) видно, что чем мельче древовидное разбиение (чем больше вершин в
фактор-графе), тем меньше объем возникающего заполнения, поэтому после
построения грубого древовидного разбиения целесообразно измельчить его.

Страницы