MO640 - Questão para a prova oral

Número: 042

Enunciado:
Considerando as seguintes afirmações sobre grafos de arestas coloridas, baseado no texto de Hannenhalli e Pevzner:

1. Um ciclo neste tipo de grafo é dito alternado se as cores de duas arestas consecutivas são sempre distintas
2. O comprimento de um ciclo alternado é o número total de arestas que ele possui
3. Um ciclo alternado é dado como pequeno se seu comprimento é igual a 2, e grande se maior que dois
4. Uma permutação π é simples seu grafo de breakpoints não possui ciclos longos.

1. Apenas a afirmação I está correta
2. Apenas a afirmação II está incorreta
3. Somente as afirmações I, II e III estão corretas
4. Todas as afirmações estão corretas
5. NDA

Autor(a): Bruno Dilly