Um grupo de cinco acrobatas realiza um número em que formam uma pirâmide. Neste número deve haver um caminho entre quaisquer dois acrobatas diferentes ou a pirâmide cai. Na matriz de adjacência a seguir, aij = 1 significa que Pi dá suporte a Pj

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

Quem pode ficar de fora da pirâmide sem que ela caia?

Passo 1

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

A partir da matriz de adjacência temos para:

Coluna 1

P 2 → P 1 ;   P 3 → P 1 ; P 4 → P 1

Coluna 2

P 5 → P 2

Coluna 3

P 1 → P 3 ; P 5 → P 3

Coluna 4

P 1 → P 4 ; P 3 → P 4

Coluna 5

P 2 → P 5 ; P 4 → P 5

Passo 2

Sabemos da teoria de grafos que um caminho é uma sequência de vértices distintos. A partir do que obtivemos da matriz de adjacência, vamos traçar um caminho a partir do vértice 1:

P 1 → P 3 → P 4 → P 5 → P 2

Ou

P 1 → P 4 → P 5 → P 2

Lembrando que só podemos usar o que temos no passo 1, e sem repetir um vértice já usado. Logo, o vértice que pode ser removido é P3.

Resposta

P3.