073-2004

MO640 - Questão para a prova oral
Número: 073
Enunciado:
Considerando o grafo de sobreposições definido por A. Bergeron no artigo "A Very Elementary Presentation of the Hannenhalli-Pevzner Theory", se um vértice v de um grafo de sobreposições é orientado, então podemos afirmar que:

1. Há no máximo uma componente orientada no grafo de sobreposições.
2. Há pelo menos um vértice orientado u ≠v na componente conexa de v.
3. Há exatamente uma componente orientada no grafo de sobreposições.
4. Há pelo menos uma componente orientada no grafo de sobreposições que não contém v.
5. NDA

Autor: José Augusto Amgarten Quitzau