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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

13
8.1. Алгоритм построения графа исключения G
k+1
(граф G
k
известен)
1) Из графа G
k
удаляется k-ая вершина вместе со всеми инцидентными ей
ребрами.
2) Все вершины графа G
k
, которые были смежны с удаленной вершиной,
соединяются ребрами.
В результате получается граф G
k+1
, соответствующий A
k+1
.
Задача 41
.
Построить граф исключения G
k
для графа G.
8.2. Алгоритм определения множества достижимости Reach(v,Q)
для графа G
1) Присваиваем вершине v первый номер и полагаем L
1
=v.
2) Для k=2 определяем множество смежности Adj(L
1
) и помечаем все
вершины этого множества, а для Adj(L
1
) делаем следующее: если вершина
u из Adj(L
1
) принадлежит Q, то относим ее к множеству L
2
, а если не
принадлежит, то относим ее к множеству Reach(v,Q) и полагаем k=3.
3) На k-ом шаге определяем множество Adj(L
k-1
) из непомеченных вершин,
помечаем их и для каждого u
∈
Adj(L
k-1
) выполняем следующее: если u из
Adj(L
k-1
) принадлежит Q, то u
∈
L
k
, если нет - u
∈
Reach(v,Q). Если все u
∉
Q,
то L
k
=
∅
и алгоритм закончен. Иначе идем на 4).
4) Полагаем k = k + 1 и, если остались непомеченные вершины,
принадлежащие Adj(L
k
)
∩
Q, идём на 3).
Задача 42
.
Реализовать алгоритм определения множества достижимости для
графа G и Q={2, 6, 8}.
1 2 3 4 7
5 9 8
3 4 7
6
5 9 8
4 7
6
5 9 8
9
2 3 4 7
6
5 9 8
G
2
G
3
G
4
1 2
6
3 4 7
5 8
G
1
≡
G
7
6
9 8
G
6
9
7
6
5 8
G
5
7
9 8
9 8 9 G
7
G
8
G
9
                                                                                13

   8.1. Алгоритм построения графа исключения Gk+1 (граф Gk известен)

1) Из графа Gk удаляется k-ая вершина вместе со всеми инцидентными ей
   ребрами.
2) Все вершины графа Gk, которые были смежны с удаленной вершиной,
   соединяются ребрами.
   В результате получается граф Gk+1, соответствующий Ak+1.

Задача 41. Построить граф исключения Gk для графа G.

    11             22               33               44           77                      2           3        4       7
                        6                                                        G2           6
  G1≡G
                                    55               99           88                                  5        9       8

                                3                4            7                                            4       7
   G3                                                                            G4       6
               6
                                5                9            8                                   5        9       8

                                                          7                                                        7
   G5                                                                           G6
               6                                                                          6
                            5                9            8                                                9       8


                                         7
           7
         G                                                             G8   9         8               G9   9
                        9                8



         8.2. Алгоритм определения множества достижимости Reach(v,Q)
                                 для графа G

1) Присваиваем вершине v первый номер и полагаем L1=v.
2) Для k=2 определяем множество смежности Adj(L1) и помечаем все
   вершины этого множества, а для Adj(L1) делаем следующее: если вершина
   u из Adj(L1) принадлежит Q, то относим ее к множеству L2, а если не
   принадлежит, то относим ее к множеству Reach(v,Q) и полагаем k=3.
3) На k-ом шаге определяем множество Adj(Lk-1) из непомеченных вершин,
   помечаем их и для каждого u∈Adj(Lk-1) выполняем следующее: если u из
   Adj(Lk-1) принадлежит Q, то u∈Lk, если нет - u∈Reach(v,Q). Если все u∉Q,
   то Lk=∅ и алгоритм закончен. Иначе идем на 4).
4) Полагаем     k = k + 1 и, если остались непомеченные вершины,
   принадлежащие Adj(Lk)∩Q, идём на 3).

Задача 42. Реализовать алгоритм определения множества достижимости для
           графа G и Q={2, 6, 8}.

Страницы