Considere uma rede de comunicações entre cinco pessoas com matriz de adjacência
- P3 pode mandar uma mensagem a P5 em no máximo dois estágios?
- 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)?
- 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:
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.
Temos um mínimo de 4 estágios.
Resposta
Ver passo a passo.