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 - RA962569