Considere um grafo simples G = (V, A) euleriano. Sobre G é possível afirmar que: a ) o grau de todos os seus vértices é ímpar. b ) possui laços. c ) é um grafo completo. d ) a soma dos graus dos vértices não adjacentes é maior ou igual a |V|. e ) o grau de todos os seus vértices é par.

a ) o grau de todos os seus vértices é ímpar.
b ) possui laços.
c ) é um grafo completo.
d ) a soma dos graus dos vértices não adjacentes é maior ou igual a |V|.
e ) o grau de todos os seus vértices é par.

Question

Considere um grafo simples G = (V, A) euleriano. Sobre G é possível afirmar que: a ) o grau de todos os seus vértices é ímpar. b ) possui laços. c ...

Ed · Answer

Para um grafo ser euleriano, ele deve atender a certas condições. Um grafo é considerado euleriano se existe um ciclo que percorre todas as arestas exatamente uma vez. As condições para que um grafo simples seja euleriano são:

1. Todos os vértices do grafo devem ter grau par.
2. O grafo deve ser conexo (exceto se tiver vértices isolados).

Agora, vamos analisar as alternativas:

a) O grau de todos os seus vértices é ímpar. - FALSO, pois em um grafo euleriano, todos os vértices devem ter grau par.

b) Possui laços. - FALSO, um grafo simples não pode ter laços.

c) É um grafo completo. - FALSO, um grafo euleriano não precisa ser completo.

d) A soma dos graus dos vértices não adjacentes é maior ou igual a |V|. - Esta afirmação não é uma condição necessária para um grafo ser euleriano.

e) O grau de todos os seus vértices é par. - VERDADEIRO, esta é a condição correta para que um grafo seja euleriano.

Portanto, a alternativa correta é: e) o grau de todos os seus vértices é par.

Ed · Answer

Para um grafo ser euleriano, é necessário que todos os seus vértices tenham grau par, exceto no máximo dois vértices que podem ter grau ímpar (esses são os extremos do caminho euleriano ou um ciclo euleriano).

Analisando as opções:
a) o grau de todos os seus vértices é ímpar - Incorreto, pois em um grafo euleriano, o grau de todos os vértices é par, exceto no máximo dois vértices.
b) possui laços - Não é uma característica determinante para um grafo ser euleriano.
c) é um grafo completo - Não é uma condição para um grafo ser euleriano.
d) a soma dos graus dos vértices não adjacentes é maior ou igual a |V| - Não é uma propriedade de grafos eulerianos.
e) o grau de todos os seus vértices é par - Correto, pois em um grafo euleriano, todos os vértices têm grau par, exceto no máximo dois vértices.

Portanto, a alternativa correta é: e) o grau de todos os seus vértices é par.

Matemática Discreta

Avaliação - TEORIA DOS GRAFOS (Prova Online)

Respostas

Crie sua conta grátis para liberar essa resposta. 🤩

Ainda com dúvidas?

Essa pergunta também está no material:

Avaliação - TEORIA DOS GRAFOS (Prova Online)

Mais conteúdos dessa disciplina