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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

12
Таким образом, v = 2 или v = 5 искомые вершины (даже периферийные).
§8. Некоторые понятия из теории графов
Рассмотрим столбцовую схему метода Гаусса.
На k-ом шаге получили k-ую промежуточную матрицу A
k
.
Опр.
Граф G
k
, соответствующий матрице A
k
, называется
графом
исключения матрицы A
k
,G
1
≡
G
(или k-ым графом
исключения матрицы A
k
).
Опр.
Графом заполнения G
F
матрицы А называется граф,
который содержит все вершины и ребра матрицы А, а
также все ребра всех графов исключения.
Заметим, что после гауссова исключения получается матрица, которая не
является симметричной, поэтому графу заполнения G
F
отвечает матрица U+U
T
,
а не матрица U.
Опр.
Если для данного графа G и подмножества его вершин Q выбраны две не
совпадающие вершины u, v, не принадлежащие Q, то будем говорить, что
вершина v
достижима из вершины u через Q
в случае, когда либо вершины
u,v – смежные, либо u,v соединены путем, все вершины которого, кроме
начальной и конечной, принадлежат Q.
Опр
.
Для заданного множества Q и вершины u, не принадлежащей Q,
достижимое множество Reach(u,Q) из u через Q определяется как множество
всех вершин, достижимых из u через Q. Таким образом,
Ι
∅
∅∅
∅=
==
=
QQuach
),(Re
.
Заметим, что если Q пусто или если вершина u не принадлежит Adj(Q), то
в этом случае
)(),(Re uAd
j
Quach
=
==
=
.
Задача 40
.
Для графа G найти Reach(1,Q), Reach(9,Q), Reach(7,Q), где
Q={2,8}.
A
k
0
Reach (1,Q)={3}.
Reach (9,Q)={5,7}.
Reach (7,Q)={4,5,9}.
1 2 3 4 7
5 8 9 6 
                                    12

  Таким образом, v = 2 или v = 5 искомые вершины (даже периферийные).

                §8. Некоторые понятия из теории графов
  Рассмотрим столбцовую схему метода Гаусса.

                   На k-ом шаге получили k-ую промежуточную матрицу Ak.

                     Опр. Граф Gk, соответствующий матрице Ak, называется
                     графом исключения матрицы Ak,G1≡G (или k-ым графом
       0      Ak     исключения матрицы Ak ).
                     Опр. Графом заполнения GF матрицы А называется граф,
                     который содержит все вершины и ребра матрицы А, а
также все ребра всех графов исключения.

   Заметим, что после гауссова исключения получается матрица, которая не
является симметричной, поэтому графу заполнения GFотвечает матрица U+UT,
а не матрица U.

Опр. Если для данного графа G и подмножества его вершин Q выбраны две не
  совпадающие вершины u, v, не принадлежащие Q, то будем говорить, что
  вершина v достижима из вершины u через Q в случае, когда либо вершины
  u,v – смежные, либо u,v соединены путем, все вершины которого, кроме
  начальной и конечной, принадлежат Q.
Опр. Для заданного множества Q и вершины u, не принадлежащей Q,
  достижимое множество Reach(u,Q) из u через Q определяется как множество
  всех вершин, достижимых из u через Q. Таким образом,
  Re ach( u, Q )Ι Q =∅ .

     Заметим, что если Q пусто или если вершина u не принадлежит Adj(Q), то
  в этом случае Re ach( u, Q ) = Adj ( u) .

Задача 40. Для графа G найти Reach(1,Q), Reach(9,Q), Reach(7,Q), где
           Q={2,8}.

        1      2       3       4         7
                                                 Reach (1,Q)={3}.
                                                 Reach (9,Q)={5,7}.
                                                 Reach (7,Q)={4,5,9}.
               6       9       8         5

Страницы