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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

23
1) по возможности следует выбирать минимальный из всех разделителей
(идеально – разделитель, состоящий из одной вершины);
2) разделитель следует выбирать таким образом, чтобы возникающие
компоненты связности имели примерно одинаковый размер (для того
чтобы нулевые блоки были больше).
Опр.
Разделитель называется минимальным, если никакое его собственное
подмножество не является разделителем.
11.2. Алгоритм метода вложенных сечений
Пусть есть граф G(V,E). Пусть С – множество вершин всех разделителей,
которые будут возникать в процессе реализации алгоритма, который
закончится, когда в С попадут все вершины.
1)
C =
∅
, n =
V
(число вершин графа G).
2)
Если n = 0 - алгоритм закончен, иначе рассматривается граф G(V\C) (из
исходного графа G удаляются все вершины из С вместе с инцидентными им
ребрами). Находим связную компоненту G(R) этого графа с множеством
вершин R и ищем в G(R) ППВ u.
3)
Строим в G(R) СУС L
0,
L
1
,..., L
m
с корнем u. Если m<2 , то полагаем S = R и
переходим к 5). Иначе (m
≥
2) в СУС выбираем средний уровень L
j,
где
j = [(m+1)/2].
4)
В множестве L
j
выбираем подмножество S, которое является минимальным
разделителем графа G(R) среди всех разделителей, которые содержатся в
множестве L
j.
5)
Множество S принимаем в качестве нового члена разбиения. Полагаем
С = С
∪
S и нумеруем вершины разделителя S числами от n –
S
+1 до n.
6)
Полагаем n = n –
S
и идем на 2), пока не пройдем все вершины.
Трудность этого алгоритма связана с нахождением минимального
разделителя. Поэтому вместо минимального часто ищут ,,не слишком
большой’’.
Замечание.
Для шага 4) в качестве разделителя S можем взять совокупность
всех вершин уровня L
j
, которые смежны с вершинами уровня L
j+1
. Для
нахождения объема заполнения нужно посчитать площадь заштрихован-
ных фигур.
Задача 49.
Для графа G из задачи 46 реализовать алгоритм вложенных сечений
и нарисовать переупорядоченную матрицу. 
                                     23

   1) по возможности следует выбирать минимальный из всех разделителей
      (идеально – разделитель, состоящий из одной вершины);
   2) разделитель следует выбирать таким образом, чтобы возникающие
      компоненты связности имели примерно одинаковый размер (для того
      чтобы нулевые блоки были больше).

Опр. Разделитель называется минимальным, если никакое его собственное
  подмножество не является разделителем.


                11.2. Алгоритм метода вложенных сечений

   Пусть есть граф G(V,E). Пусть С – множество вершин всех разделителей,
которые будут возникать в процессе реализации алгоритма, который
закончится, когда в С попадут все вершины.
1) C = ∅, n = V (число вершин графа G).
2) Если n = 0 - алгоритм закончен, иначе рассматривается граф G(V\C) (из
   исходного графа G удаляются все вершины из С вместе с инцидентными им
   ребрами). Находим связную компоненту G(R) этого графа с множеством
   вершин R и ищем в G(R) ППВ u.
3) Строим в G(R) СУС L0,L1,..., Lm с корнем u. Если m<2 , то полагаем S = R и
   переходим к 5). Иначе (m≥2) в СУС выбираем средний уровень Lj, где
   j = [(m+1)/2].
4) В множестве Lj выбираем подмножество S, которое является минимальным
   разделителем графа G(R) среди всех разделителей, которые содержатся в
   множестве Lj.
5) Множество S принимаем в качестве нового члена разбиения. Полагаем
   С = С∪S и нумеруем вершины разделителя S числами от n – S+1 до n.
6) Полагаем n = n – S и идем на 2), пока не пройдем все вершины.

   Трудность этого алгоритма связана с нахождением минимального
разделителя. Поэтому вместо минимального часто ищут ,,не слишком
большой’’.

Замечание. Для шага 4) в качестве разделителя S можем взять совокупность
     всех вершин уровня Lj , которые смежны с вершинами уровня Lj+1 . Для
     нахождения объема заполнения нужно посчитать площадь заштрихован-
     ных фигур.


Задача 49. Для графа G из задачи 46 реализовать алгоритм вложенных сечений
       и нарисовать переупорядоченную матрицу.

Страницы