MO640 - Questão para a prova oral

Número: 012

 

Enunciado:

Qual das afirmações abaixo é correta?

  1. Se G é um grafo onde o grau de cada vértice é pelo menos dois, então G não contém ciclos.
  2. Em um grafo qualquer, há um número impar de vértices de grau impar.
  3. Algoritmos com as seguintes complexidades são considerados polinomiais: O(1), O(n2), O(2n), O( |V|3 + |E|3 ), O(n). 
  4. Para que um grafo tenha um caminho euleriano todos os seus vértices devem ter grau par.
  5. NDA

Autor(a): Pedro de Vasconcellos Castro.