Determine quando o digráfico com matriz de adjacência dada é fortemente conexo.

a ) 0 0 1 1 1 1 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0

b ) 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0

Passo 1

E aí pessoal, belezinha. Vamos agora trabalhar em algumas questões da teoria de grafos.

Seguindo o que fora desenvolvido no exemplo 14, devemos calcular a matriz E, dada pela soma de A até An-1.

Item a

Como a matriz dada é de ordem n = 5, E = A + A2 + A3 + A4. Calculando as multiplicações da matriz A teremos:

A 2 = 0 0 1 1 1 1 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0 ∙ 0 0 1 1 1 1 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0 = 1 3 0 0 1 0 2 1 1 2 1 2 1 0 1 0 1 1 2 1 1 2 0 0 1

E

A 3 = 1 3 0 0 1 0 2 1 1 2 1 2 1 0 1 0 1 1 2 1 1 2 0 0 1 ∙ 0 0 1 1 1 1 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0 = 4 1 4 4 1 4 4 2 2 1 0 1 1 2 2 5 1 3 1 1 3 1 2 3 3

E

A 4 = A 2 ∙ A 2 = 1 3 0 0 1 0 2 1 1 2 1 2 1 0 1 0 1 1 2 1 1 2 0 0 1 ∙ 1 3 0 0 1 0 2 1 1 2 1 2 1 0 1 0 1 1 2 1 1 2 0 0 1 = 2 6 5 5 8 5 5 8 8 6 4 5 8 4 9 5 2 3 6 2 3 6 1 4 2

Temos que:

E = 0 0 1 1 1 1 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0 + 1 3 0 0 1 0 2 1 1 2 1 2 1 0 1 0 1 1 2 1 1 2 0 0 1 + 4 1 4 4 1 4 4 2 2 1 0 1 1 2 2 5 1 3 1 1 3 1 2 3 3 + 2 6 5 5 8 5 5 8 8 6 4 5 8 4 9 5 2 3 6 2 3 6 1 4 2 =

= 7 10   10 10 11 10 11 12   12 9 5 8 11 7 13 11     4 7 9     4 7 9   3 8 6

Como todos os elementos em E são positivos, o digráfico dado é fortemente conexo.

Passo 2

Item b

Como a matriz dada é de ordem n = 5, E = A + A2 + A3 + A4. Calculando as multiplicações da matriz A teremos:

A 2 = 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 ∙ 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 = 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 2 0 1 0 1 0

E

A 3 = 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 2 0 1 0 1 0 ∙ 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 = 1 0 0 0 0 0 0 1 2 1 2 0 1 1 0 0 0 0 0 0 1 0 1 0 1

E

A 4 = A 2 ∙ A 2 = 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 2 0 1 0 1 0 ∙ 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 2 0 1 0 1 0 = 0 0 0 0 1 2 1 0 2 1 0 1 0 0 0 0 1 0 0 2 1 1 2 0 1

Temos que:

E = 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 + 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 2 0 1 0 1 0 + 1 0 0 0 0 0 0 1 2 1 2 0 1 1 0 0 0 0 0 0 1 0 1 0 1 + 0 0 0 0 1 2 1 0 2 1 0 1 0 0 0 0 1 0 0 2 1 1 2 0 1 =

= 1 0 0 1 2 3 2 2 5 3 2 2 2 2 0 0 2 0 0 4 2 3 4 1 2

Como temos elementos nulos em E, o digráfico dado não é fortemente conexo.

Resposta

Ver passo a passo.