Question

Considere o grafo não orientado, cuja matriz de adjacência é dada abaixo open parentheses table row 0 1 0 0 1 0 row 1 0 1 0 0 0 row 0 1 0 1 1 0 row 0 0 1 0 1 0 row 1 0 1 1 0 1 row 0 0 0 0 1 0 row blank end table close parentheses

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. I e II, apenas.
b. I e III, apenas.
c. II, apenas.
d. I, apenas.
e. II e III, apenas.

Answer 1

Resposta:

Alternativa d. I, apenas

Explicação passo a passo:

Conferido no Gabarito.

O grafo tem exatamente 2 nós com grau ímpar 4 nós com grau par totalizando 6 nós.

Answer 2

Alternativa D está correta. O caminho N1⇒N2⇒N3⇒N4⇒N5⇒N6 é um caminho que passa por todos os nós apenas uma vez, por isso este grafo admite um caminho de Euler.

Identificando um caminho de Euler

• Um caminho de Euler ocorre quando é possível passar por todos os nós de um grafo apenas uma vez.
• A visualização de um possível caminho Euleriano é facilitada quando transformamos a matriz de adjacência em um diagrama.
• A partir da visualização do diagrama é possível identificar que podemos percorrer o caminho N1⇒N2⇒N3⇒N4⇒N5⇒N6, passando por todos os nós apenas uma vez
• Por isso, a afirmação I está correta.

Identificar o grau de um nó

• O grau de um nó é definido pelo número de ligações com outros nós.
• Cada linha da matriz de adjacência representa um nó de um grafo.
• Para identificar o grau de um nó a partir da matriz de adjacência, devemos somar as linhas da matriz.

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  

• Os únicos nós com grau ímpar são N3 e N6, portanto a afirmação II está incorreta.

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

• Para identificar o número de nós de um grafo a partir da matriz de adjacência, devemos verificar as dimensões que esta matriz possui.
• Esta matriz possui dimensões 6x6, logo este grafo possui 6 nós. Por isso a

A única afirmação correta é a I, portanto a alternativa D está incorreta

Para saber mais sobre grafos, acesse:

https://brainly.com.br/tarefa/52791402

https://brainly.com.br/tarefa/52947924

#SPJ2