Considere o grafo não orientado, cuja matriz de adjacência é dada abaixo:
Considere as afirmativas abaixo:

I) O grafo admite um caminho de Euler.
II) Existem três nós com grau ímpar.
III)O grafo possui cinco nós.

Estão corretas as afirmativas:
a.

II, apenas.
b.

I e III, apenas.
c.

I, apenas.
d.

II e III, apenas.
e.

I e II, apenas.

Anexos:

Respostas

respondido por: silvarpj

Resposta:

Alternativa C

Explicação passo a passo:

I - Verdadeiro

II - Falso

III - Falso

respondido por: Hiromachi

Alternativa D está correta, apenas a afirmação I é verdadeira. Este grafo possuí diversos caminhos de Euler, um é a trajetória N1⇒N2⇒N3⇒N4⇒N5⇒N6.

Identificando um caminho de Euler

Um caminho de Euler é um caminho que visita todos os nós de um grafo uma vez.

A melhor de identificar um possível caminho Euleriano é transformar a matriz de adjacência em um diagrama, apresentado no fim desta resolução.

Com o auxílio do diagrama é possível identificar que o caminho N1⇒N2⇒N3⇒N4⇒N5⇒N6 passa por todos os nós apenas uma vez.

Logo concluímos que a afirmação I está correta.

Identificar o grau de um nó

O grau de um nó é são os números de ligações que um vértice possuí.

Cada linha da matriz de adjacência indica quais ligações cada nó possuí. Por exemplo, a 1ª linha da matriz indica que o nó nº 1 possuí ligação com o 2º e o 5º nó.

Quando somamos as linha da matriz de adjacência encontramos o grau de cada nó.

g(N1) = 1 + 1 = 2

g(N2) = 1 + 1 = 2

g(N3) = 1 + 1 + 1 = 3

g(N4) = 1 + 1 = 2

g(N5) = 1 + 1 + 1 + 1 = 4

g(N6) = 1

Após somar todas as linhas, identificamos que apenas os nós N3 e N6 possuem grau ímpar, portanto a afirmação II está incorreta.

Identificando o número de nós de um grafo

Como cada linha representa um nó de um grafo, o número de linhas presentes na matriz de adjacência indicam o número de nós que um grafo possuí.