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

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

b ) 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 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 = 4, E = A + A2 + A3. Calculando as multiplicações da matriz A teremos:

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

E

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

Temos que:

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

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 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 ∙ 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 = 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 1

E

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

E

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

Temos que:

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

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

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

Resposta

Ver passo a passo.