Considere uma rede de comunicações entre cinco pessoas com matriz de adjacência

0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0

  1. P3 pode mandar uma mensagem a P5 em no máximo dois estágios?
  2. Qual o número mínimo de estágios que garantirão que todas as pessoas possam receber uma mensagem de qualquer outra pessoa (diferente)?
  3. Qual o número mínimo de estágios que garantirão que todas as pessoas possam receber uma mensagem de qualquer outra pessoa (incluindo ela mesma)?

Passo 1

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

Item a

De acordo com a teoria de grafos, temos as linhas representando a saída de um vértice, e as colunas a chegada naquele vértice, ou seja, quando uma coluna tem o valor 1 em um de seu elementos, houve a chegada no vértice P com índice igual ao daquela coluna.

Para que a informação chegasse de P3 a P5 em no máximo dois estágios temos apenas duas possibilidades: 1) Sair de P3 e chegar em P5 (um estágio); 2) Sair de P3 para outro vértice, e deste para P5 (dois estágios). Observando a matriz vemos que a primeira possibilidade não ocorre, pois o elemento que se encontra na terceira linha e quinta coluna é nulo.

Ainda observando a matriz dada, temos na quinta coluna (referente a chegada de informação em P5), o valor 1 apenas no elemento da segunda linha, ou seja, a informação sai de P2 e chega em P5 (Que nos dá um estágio no envio da informação). Para termos no máximo dois estágios, a informação deverá sair de P3 e chegar em P2 (primeiro estágio), para poder depois ir de P2 a P5 (segundo estágio). Verificando o elemento da terceira linha e segunda coluna, temos um valor nulo, o que significa que não há a possibilidade de envio da informação de P3 a P5 em no máximo dois estágios.

Passo 2

Item b

Devemos construir os caminhos para chegar com a informação em cada um dos vértices. Verificamos na primeira coluna onde temos um elemento igual a 1 (referente a chegada da informação em P1), e verificamos a qual linha esse elemento pertence (referente de onde saiu a informação), e seguimos esse procedimento sucessivamente até termos usado todos os vértices:

P 1 ← P 4 ← P 3 ← P 2   ( 3   e s t á g i o s )

P 1 ← P 4 ← P 5   2   e s t á g i o s

P 2 ← P 1 ← P 4   2   e s t á g i o s

P 2 ← P 4 ← P 3   2   e s t á g i o s

P 2 ← P 4 ← P 5   2   e s t á g i o s

P 3 ← P 2 ← P 1   2   e s t á g i o s

P 3 ← P 2 ← P 4   2   e s t á g i o s

P 3 ← P 5   ( 1   e s t á g i o )

P 4 ← P 3 ← P 2 ← P 1   3   e s t á g i o s

P 4 ← P 3 ← P 5   2   e s t á g i o s

P 4 ← P 5 ← P 2   2   e s t á g i o s

P 5 ← P 2 ← P 1 ← P 4   3   e s t á g i o s

P 5 ← P 2 ← P 4 ← P 3   3   e s t á g i o s

Temos um mínimo de 3 estágios.

Passo 3

Item c

Para receber uma mensagem de si próprio, incluímos a participação novamente do mesmo vértice.

P 1 ← P 4 ← P 3 ← P 2 ← P 1   ( 4   e s t á g i o s )

P 1 ← P 4 ← P 5   2   e s t á g i o s

P 2 ← P 1 ← P 4   2   e s t á g i o s

P 2 ← P 4 ← P 3 ← P 2   3   e s t á g i o s

P 2 ← P 4 ← P 5   2   e s t á g i o s

P 3 ← P 2 ← P 1 ← P 4   3   e s t á g i o s

P 3 ← P 2 ← P 4 ← P 3   3   e s t á g i o s

P 3 ← P 5   ( 1   e s t á g i o )

P 4 ← P 3 ← P 2 ← P 1 ← P 4   4   e s t á g i o s

P 4 ← P 3 ← P 5   2   e s t á g i o s

P 4 ← P 5 ← P 2   2   e s t á g i o s

P 5 ← P 2 ← P 1 ← P 4 ← P 3   4   e s t á g i o s

P 5 ← P 2 ← P 1 ← P 4 ← P 5   ( 4   e s t á g i o s )

P 5 ← P 2 ← P 4 ← P 3   3   e s t á g i o s

Temos um mínimo de 4 estágios.

Resposta

Ver passo a passo.