litceysel.ru
добавить свой файл
1
Лекция 6


Транзитивное замыкание графа.


Пусть G=(A,R) – ориентированнй граф.

Транзитивный замыканием графа G называется граф G*=(A,R*), в котором из v в w из A идёт ребро тогда и только тогда, если существует путь (длины 0 или больше) из v в w.

Если (a,b)R и (b,c)R => (a,b)R*, (b,c)R*, (a,c)R*


Алгоритм 1: (