Algoritimo Marshall

Algoritmo de Warshall

a) O algoritmo de Floyd-Warshall é utilizado para resolver problemas com grafos orientados. Uma de suas aplicações é encontrar o fecho transitivo entre relações, e é o que será utilizado para o desenvolvimento deste exercício.

b) R = {(a,a),(a,b),(b,b),(b,d),(b,e),(c,a),(c,c),(d,a),(d,e),(e,e)}

Dígrafo Inicial

a

b e d

c

Matriz Inicial: a b c a 1 1 0 b 0 1 0 c 1 0 1 d 1 0 0 e 0 0 0

d
0
1
0
0
0

e
0
1
0
1
1

Partindo da matriz inicial e utilizando o par “a,a” como referencia, obtemos a seguinte matriz MA:
Matriz MA a b c d e a 1 1 0 0 0 b 0 1 0 1 1 c 1 1 1 0 0 d 1 1 0 0 1 e 0 0 0 0 1
Note as mudanças em destaque.

Tomamos agora o par “b,b” como referencia para obter a matriz MB:
Matriz MB a b c d e a 1 1 0 1 1 b 0 1 0 1 1 c 1 1 1 1 1 d 1 1 0 0 1 e 0 0 0 0 1
Novamente mudanças são apresentadas.

Tomamos agora o par “c,c” como referência para obter a matriz MC:

Matriz MC a b c d e a 1 1 0 1 1 b 0 1 0 1 1 c 1 1 1 1 1 d 1 1 0 0 1 e 0 0 0 0 1
Nada muda com o par “c,c” como referência.

Tomamos agora o par “d,d” como referência para obter a matriz MD:

Matriz MD a b c d e a 1 1 0 1 1 b 1 1 0 1 1 c 1 1 1 1 1 d 1 1 0 0 1 e 0 0 0 0 1
Mais uma vez mudanças aparecem.

Tomamos agora o par “e,e” como referência para obter a matriz ME:

Matriz ME a b c d e a 1 1 0 1 1 b 1 1 0 1 1 c 1 1 1 1 1 d 1 1 0 0 1 e 0 0 0 0 1
Nada foi alterado na matriz ME. E chegamos a nossa Matriz final.

Dígrafo final – Fecho transitivo:

a

b e c

d