Question

Considere um grafo não-orientado, com 4 nós, 1, 2, 3 e 4. Assinale a alternativa abaixo, que apresenta uma matriz de adjacência, que dê origem a um grafo que possui um circuito hamiltoniano.

Answer 1

Resposta:

alternativa b, conferido no AVA

Explicação passo a passo:

Answer 2

Alternativa B. Para resolvermos esta questão precisamos verificar se cada alternativa possuí um circuito hamiltoniano.

Conferindo as matrizes de adjacência

• A matriz de adjacência é uma forma de representação de um grafo em formato de matriz, possuindo as seguintes propriedades:

1. É uma matriz quadrada onde a ordem da matriz possuem o valor da quantidade de nós que o grafo possuí.
2. Cada linha representa um nó e indica quais ligações este nó possuí
3. Quando o nó i possuí uma ligação com o nó j, o valor de aij será 1, caso contrário aij será 0.

• Um circuito hamiltoniano é um caminho que passa por todos vértices apenas uma vez e retorna para o vértice de origem.
• Analisando as matrizes apresentadas podemos eliminar algumas alternativas:

1. Alternativa A: O nó 4 possuí apenas um vértice adjacente, fazendo com que o caminho não possa ser feito. Por isso a alternativa A está incorreta.
2. Alternativa C: O nó 4 possuí apenas um vértice adjacente, fazendo com que o caminho não possa ser feito. Por isso a alternativa C está incorreta.    
3. Alternativa D: Os nós 1 e 4 possuem apenas um vértice adjacente, fazendo com que o caminho não possa ser feito. Por isso a alternativa D está incorreta.    
4. Alternativa E: O nó 1 está isolado, fazendo com que o caminho não possa ser feito. Por isso a alternativa E está incorreta.    

• A alternativa B permite um caminho hamiltoniano começando por qualquer vértice, conforme a figura no final desta resolução. Por isso a alternativa B está correta.

Para saber mais grafos, acesse:

brainly.com.br/tarefa/43635169

brainly.com.br/tarefa/21950329

#SPJ2