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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

19
10.3. Алгоритм измельченного фактор-дерева
Возможность измельчения древовидного разбиения связана с тем, что
каждый из УС L
i
может оказаться несвязным множеством, т. е. распадаться на
несколько несвязных компонент связности:
(если же L
i
связно, то измельчения не сделаешь). В этом случае древовидное
разбиение измельчают, отождествляя не все вершины, а лишь вершины каждой
компоненты связности, т.е. будем иметь вершины
k
iii
LLL
,...,,
21
.
Таким образом, увеличиваем число вершин фактор-графа и уменьшаем
блоки.
В матричной интерпретации построение фактор-графа означает
следующее: каждый элемент на главной диагонали отвечает своему УС,
каждый из которых (если есть несколько компонент связности) разбивается на
блоки, внутри которых можем выделить блоки, состоящие из нулей.
Таким образом, необходимо найти компоненты связности
k
iii
LLL
,...,,
21
.
Алгоритм
1) Полагаем i=0. В качестве корневой желательно взять периферийную
вершину. При построении СУС все рёбра графа разделим на древесные и
поперечные. К древесным относятся рёбра, соединяющие вершины
различных УС, к поперечным - одного.
2) Полагаем i=1.
3) Возьмём некоторую вершину из L
i
и построим корневую структуру с
корнем в этой вершине, используя при построении только поперечные рёбра.
При этом мы останемся на прежнем уровне, и если у L
i
есть несколько
компонент связности, то в какой-то момент мы исчерпаем все компоненты
связности L
i
и, следовательно, сможем выделить компоненту связности
1
i
L
.
Затем возьмём другую вершину, не принадлежащую
1
i
L
, – получим
2
i
L
и т.д.
4) Если i<m, то i=i+1 и идём на 3). Иначе алгоритм закончен.
10.4. Примеры
Задача 46
.
Построить для графа G его фактор-дерево, используя СУС, и указать
монотонное упорядочение (обратную перенумерацию) фактор-дерева.
Показать частичный граф, отвечающий уровням L
4,
L
5,
L
6.
k
i
2
i
1
ii
L...LLL
∪
∪∪
∪∪
∪∪
∪∪
∪∪
∪=
==
=
                                       19

           10.3. Алгоритм измельченного фактор-дерева

    Возможность измельчения древовидного разбиения связана с тем, что
каждый из УС Li может оказаться несвязным множеством, т. е. распадаться на
несколько несвязных компонент связности:
                            L i =L i ∪ L i ∪ ... ∪ L i
                                   1        2            k
(если же Li связно, то измельчения не сделаешь). В этом случае древовидное
разбиение измельчают, отождествляя не все вершины, а лишь вершины каждой
компоненты связности, т.е. будем иметь вершины Li1 , Li2 ,..., Lik .
   Таким образом, увеличиваем число вершин фактор-графа и уменьшаем
блоки.
   В матричной интерпретации        построение     фактор-графа        означает
следующее: каждый элемент на главной диагонали отвечает своему УС,
каждый из которых (если есть несколько компонент связности) разбивается на
блоки, внутри которых можем выделить блоки, состоящие из нулей.
   Таким образом, необходимо найти компоненты связности Li1 , Li2 ,..., Lik .

                                   Алгоритм
1) Полагаем i=0. В качестве корневой желательно взять периферийную
   вершину. При построении СУС все рёбра графа разделим на древесные и
   поперечные. К древесным относятся рёбра, соединяющие вершины
   различных УС, к поперечным - одного.
2) Полагаем i=1.
3) Возьмём некоторую вершину из Li и построим корневую структуру с
   корнем в этой вершине, используя при построении только поперечные рёбра.
   При этом мы останемся на прежнем уровне, и если у Li есть несколько
   компонент связности, то в какой-то момент мы исчерпаем все компоненты
   связности Li и, следовательно, сможем выделить компоненту связности Li .
                                                                             1

  Затем возьмём другую вершину, не принадлежащую Li ,             –   получим
                                                             1

   Li2 и т.д.
4) Если i

Страницы