ВУЗ:
Составители:
Рубрика:
мент b
ij
которой равен числу ребер, инцидентных одновременно
вершинам v
i
и v
j
(в случае орграфа направленных от вершины v
i
к
вершине v
j
).
Теорема 9.2.
Матрица
n
B
дает число ориентированных мар-
шрутов длины n между любыми двумя вершинами ориентирован-
ного графа.
Доказательство
. Рассмотрим граф G=<V,E>. Пусть ⎢V ⎢= m. Ес-
ли b
ik
- число дуг, соединяющих вершину v
i
с v
k
, а b
kj
- число дуг,
соединяющих v
k
с v
j
, то b
ik
есть число различных ориентированных
маршрутов длины 2, соединяющих v
i
с v
j
и проходящих через v
k
.
Тогда
∑
=
=
m
1k
2
ijkjik
bbb
)(
есть число всех ориентированных маршрутов длины 2 между v
i
и
v
j
. Пусть теорема верна для
1n
B
−
. Покажем, что она верна для
B
B
B
1nn −
= .
Если b
ij
(n-1)
- число всех ормаршрутов длины n-1, соединяющих
v
i
с v
k
, а b
kj
- число дуг, соединяющих v
k
с v
j
, то b
ij
(n-1)
b
kj
- число
всех ормаршрутов от v
i
к v
j
, проходящих через v
k
. Тогда
)()( n
ij
m
1k
kj
1n
ik
bbb
∑
=
−
=
число всех ормаршрутов длины n от v
i
к v
j
.
Замечание 1
. Если при некотором для всех n
≥
N, то в
графе нет циклов. Если в графе нет циклов, то
0BN
n
=,
n
B
дает число про-
стых путей между любыми двумя вершинами графа.
Замечание 2
. Теорема верна и для неориентированных графов.
Список смежности
В различных алгоритмах на графах наиболее часто использует-
ся матрица смежности. При программной реализации алгоритма
хранение матрицы смежности не экономично для «слабо» связных
графов, т.к. в этом случае требуется хранение большого числа ну-
лей.
Более экономичным является хранение списка смежности.
Определение
. Списком смежности вершины v
∈
V называется
множество
35
(
)
{
}
() : ;uv wvwE=∈
(для орграфов ;vw E
∈
).
Страницы
- « первая
- ‹ предыдущая
- …
- 33
- 34
- 35
- 36
- 37
- …
- следующая ›
- последняя »
