Специальная математика. Соловьев А.Е. - 56 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

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

Рубрика: 

a b c d e f g
a 1 1
b 1
c
d 1
e 1 1
f 1 1
g 1
M M
Матрица M
2
дает все пути длиной в 2
a b c d e f g
a 1
b
c
d 1
e 1
f 1 1
g
Матрица М
n
- пути длиной в n.
Если М
i
- нулевая матрица, то наибольший путь в графе имеет длину i - 1.
Для определения наличия путей между двумя вершинами можно использовать
«транзитивное замыкание» матриц
M
*
= M
1
M
2
M
3
...
Непустая клеточка ij будет говорить о наличии пути из i-ой вершины в j-ую.
4.9. Приведение графа к ярусно-параллельной форме
Эти рассуждения имеют смысл для ориентированных графов без контуров.
Граф находится в ярусно-параллельной форме (ЯПФ),
если в нулевом ярусе размещаются вершины, имеющие нулевую полустепень захода, в i-том
ярусе - вершины, в которые заходят дуги только из предыдущих ярусов, причем хотя бы
одна дуга из (i - 1)-го яруса.
Пусть дан произвольный граф без циклов.
a
h b
g c
f d
e
a b c d e f g h
a
1
b
c
1
d
1 1
e
1 1
f
1
g
1 1
h
1 1
— 56 —
a b c d e f g
a 1 1
b 1
c
d 1
e 1 1
f 1 1
g 1
     a   b   c       d   e   f   g                     a   b   c   d   e   f   g
 a                   1   1                         a               1   1
b        1                                         b       1
c                                                  c
 d                               1                 d                           1
 e           1       1                             e           1   1
 f           1           1                         f           1       1
 g       1                                         g       1

                 M                                                 M

Матрица M2 дает все пути длиной в 2

     a   b   c       d   e   f   g
a                                1
b
c
d        1
e                                1
f        1           1
g


Матрица Мn - пути длиной в n.
Если Мi - нулевая матрица, то наибольший путь в графе имеет длину i - 1.
Для определения наличия путей между двумя вершинами можно                          использовать
«транзитивное замыкание» матриц
M* = M1  M2  M3 ...
Непустая клеточка ij будет говорить о наличии пути из i-ой вершины в j-ую.

                 4.9. Приведение графа к ярусно-параллельной форме

Эти рассуждения имеют смысл для ориентированных графов без контуров.
 Граф находится в ярусно-параллельной форме (ЯПФ),
если в нулевом ярусе размещаются вершины, имеющие нулевую полустепень захода, в i-том
ярусе - вершины, в которые заходят дуги только из предыдущих ярусов, причем хотя бы
одна дуга из (i - 1)-го яруса.
Пусть дан произвольный граф без циклов.
                       a
                                                           a   b   c   d   e   f   g   h
             h                           b             a           1
                                                       b
                                                       c       1
         g                                   c         d                   1           1
                                                       e   1                       1
                                                       f           1
                 f                   d                 g       1   1
                                                       h   1                   1

                         e




                                                 — 56 —

Страницы