ВУЗ:
Составители:
Рубрика:
С задачей определения кратчайших путей в графе тесно связана
задача транзитивного замыкания бинарного отношения. Под би-
нарным отношением на множестве V мы понимаем произвольное
подмножество E
⊆
V
×
V. Такое отношение является транзитивным,
если выполняется условие: если <x,y>
∈
E и <y,z>
∈
E, то <x,z>
∈
E
для произвольных x,y,z
∈
V. Бинарное отношение E
⊆
V
×
V можно
однозначно представить ориентированным графом G=<V,E>. Для
такого отношения определим
E
*
={<x,y>: в G=<V,E> существует путь ненулевой длины из x
в y}.
E
*
- транзитивное отношение на множестве V и E⊆E
*
.
Отношение E
*
называется транзитивным замыканием.
Если отношение E представить в виде графа G=<V,E>, то тран-
зитивное замыкание E
*
можно вычислить по алгоритму Уоршалла-
Флойда. После завершения работы алгоритма имеем:
<v
i
,v
j
>
∈
E
*
⇔
D[i,j]<
∞
При вычислении транзитивного замыкания удобно принять
⎩
⎨
⎧
∞∉><
∈><
=
). вместо ( если 0,
если 1,
E ,vv
,E,vv
W[i,j]
ji
ji
Процедура вычисления транзитивного замыкания, основанная
на алгоритме Уоршалла-Флойда, имеет следующий вид.
begin
for i=1 to n do
for j=1 to n do D[i,j]=W[i,j];
for m:=1 to n do
for i:=1 to n do
for j:=1 to n do
])j,m[D]m,i[D(]j,i[D:]j,i[D
∧
∨=
end
Здесь
∨ и ∧ - булевы операции.
После завершения работы алгоритма имеем:
⎪
⎩
⎪
⎨
⎧
∉><
∈><
=
.E ,vv
,E ,vv
D[i,j]
*
ji
*
ji
если 0,
если 1,
Матрица
n,j,i
]j,i[D
1=
называется матрицей связности (дости-
жимости) графа G=<V,E>.
56
Страницы
- « первая
- ‹ предыдущая
- …
- 54
- 55
- 56
- 57
- 58
- …
- следующая ›
- последняя »
