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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

14
1
4
2
3
65
7
8 9
64
5
31
2
G
k = 1: v = 5, L
1
= {5}.
k = 2: Adj(L
1
) = Adj(5) = {3, 6},
L
2
= {6}, Reach(5, Q) = {3}.
k = 3: Adj(L
2
) = Adj(6) = {7, 8},
L
3
= {8}, Reach(5, Q) = {3, 7}.
k = 4: Adj(L
3
) = Adj(8) = {9},
Reach(5, Q) = {3, 7, 9}.
8.3. Теорема Джорджа – Лю
Теорема
.
Пусть i
<
j и Q
i
– множество вершин с номерами меньше, чем i:
Q
i
= {v
1
, v
2
,…, v
i-1
}. Ребро (v
i
, v
j
) принадлежит графу заполнения G
F
(т.
е. элемент u
ij
матрицы заполнения отличен от нуля) тогда и только
тогда, когда v
j
∈
Reach (v
i
,Q
i
) для графа G
A
исходной матрицы.
Задача 43
.
Пользуясь теоремой Джорджа – Лю, определить, принадлежит ли
ребро (8, 9) графу заполнения G
F
.
I = 8, j = 9.
Q
8
= {1, 2, 3, 4, 5, 6,7};
Reach(8, Q
8
) = {9, 11};
{9}
∈
Reach(8, Q
8
)
⇒
(8, 9) является
ребром G
F
.
§ 9. Алгоритм минимальной степени
9.1. Алгоритм минимальной степени
Это самый простой и в общем случае самый универсальный и
эффективный алгоритм заполнения. Он состоит в следующем.
Если нужно минимизировать число ненулевых элементов матрицы U (или
U
T
), вычисляемых на k-м шаге, то достаточно просмотреть активную
подматрицу (образуемую строками матрицы A
(k)
с k-той по n-ю), выбрать
строку (или столбец) с наименьшим числом ненулевых элементов, скажем, j-ю
строку (или столбец) и переставить j-ю строку с k-той, j-тый столбец с k-тым в
матрице A
(k)
перед тем, как приступить к выполнению k-го шага исключения (т.
е. строить следующий граф исключения G
k+1
).
Так как мы оперируем не с матрицей , а с графом, то поиск строки с
наименьшим числом ненулевых элементов – это нахождение вершины
1
6
9
2
10
4
7
11
5
8
3
G
                                                       14

                                                            k = 1: v = 5, L1 = {5}.
G                             1           3                 k = 2: Adj(L1) = Adj(5) = {3, 6},
         2                5           6                            L2 = {6}, Reach(5, Q) = {3}.
                  2                               5         k = 3: Adj(L2) = Adj(6) = {7, 8},
 1                3                           7                    L3 = {8}, Reach(5, Q) = {3, 7}.
                          4           6
                                                            k = 4: Adj(L3) = Adj(8) = {9},
         4                8           9                            Reach(5, Q) = {3, 7, 9}.


                                          8.3. Теорема Джорджа – Лю

Теорема. Пусть i < j и Qi – множество вершин с номерами меньше, чем i:
        Qi = {v1, v2, , vi-1}. Ребро (vi, vj) принадлежит графу заполнения GF (т.
        е. элемент uij матрицы заполнения отличен от нуля) тогда и только
        тогда, когда vj ∈ Reach (vi,Qi) для графа GA исходной матрицы.

Задача 43. Пользуясь теоремой Джорджа – Лю, определить, принадлежит ли
      ребро (8, 9) графу заполнения GF.

     1       10        G
                                                       I = 8, j = 9.
     6                                                Q8 = {1, 2, 3, 4, 5, 6,7};
                                  8
                                                      Reach(8, Q8) = {9, 11};
     9                11                      5       {9} ∈ Reach(8, Q8) ⇒ (8, 9) является
                                                                                 ребром GF.
     2       4        7           3




                                  § 9. Алгоритм минимальной степени

                                  9.1. Алгоритм минимальной степени
     Это самый простой и в общем случае самый универсальный и
эффективный алгоритм заполнения. Он состоит в следующем.
     Если нужно минимизировать число ненулевых элементов матрицы U (или
  T
U ), вычисляемых на k-м шаге, то достаточно просмотреть активную
подматрицу (образуемую строками матрицы A(k) с k-той по n-ю), выбрать
строку (или столбец) с наименьшим числом ненулевых элементов, скажем, j-ю
строку (или столбец) и переставить j-ю строку с k-той, j-тый столбец с k-тым в
матрице A(k) перед тем, как приступить к выполнению k-го шага исключения (т.
е. строить следующий граф исключения Gk+1).
     Так как мы оперируем не с матрицей, а с графом, то поиск строки с
наименьшим числом ненулевых элементов – это нахождение вершины

Страницы