Quais das seguintes matrizes podem ser matrizes de adjacência para um digráfico de dominância?

A – 0 1 0 0 1 0 1 1 0 0 0 0 0 0 1 0

B – 0 0 1 0 1 0 0 1 0 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 0

Passo 1

Fala pessoal, tudo certinho? vamos responder mais uma questão, então prepara o material e vamos responder!!

A - A primeira linha na matriz dada implica que há uma aresta direcionada de P 1   a P 2 e P 1 a P 3 . A segunda linha implica que existem arestas direcionadas de P 2 a P 3 e P 2 para P 4 . A quarta linha implica que há uma borda direcionada de P 4 a P 3 .

Então a matriz dada pode ser matriz de adjacência do dígrafo de dominância porque (i) não há loops no grafo, pois não há aresta direcionada de nenhum vértice para em si. (ii) Se houver uma aresta direcionada de P i para P j então não há aresta de P j para P i .

Passo 2

B - A primeira linha na matriz dada implica que há uma aresta direcionada de P 1   a P 3 .

A segunda linha implica que há arestas direcionadas de P 2 para P 1 , P 2 para P 3 e P 2 para P 5 .

A terceira linha implica que há uma aresta direcionada de P 3 para P 5 .

A quarta linha implica que há arestas direcionadas de P 4 para P 1 ,   P 2 , P 3 e P 5 .

A quinta linha implica que há uma aresta direcionada de P 5 a P 1 .

Então a matriz dada pode ser matriz de adjacência do dígrafo de dominância porque (i) não há loops no grafo, pois não há aresta direcionada de nenhum vértice para em si. (ii) Se houver uma aresta direcionada de P i para P j então não há aresta de P j para P i .

Resposta

Respondida acima!