012-2004

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(n²), O(2ⁿ), O( |V|³ + |E|³ ), O(n). 
   
4. Para que um grafo tenha um circuito euleriano todos os seus vértices devem ter grau par.
   
5. NDA

Autor(a): Pedro de Vasconcellos Castro.