MO640 - Questão para a prova oral

Número: 046

Enunciado:

Um genoma "beta" sofreu um misterioso rearranjo, resultando no novo genoma "alfa". Para estudar este fenômeno, um dedicado aluno decidiu traçar um diagrama RD ("Reality and Desire Diagram", veja figura abaixo), composto por um conjunto de vértices V e arestas E.

Estudando o diagrama, o aluno encontrou uma aresta desejada (s, u) com três características curiosas:

1. Existe um conjunto V' cujos elementos são aos vértices que no diagrama encontram-se entre s e u
   
   
   
   
2. O conjunto V' não é vazio
   
   
   
   
3. Todas as arestas desejadas que incidem sobre algum vértice de V' não se entrelaçam com a aresta desejada (s, u)
   
   
   

Pode haver uma aresta (s, u) com tais características? (em outras palavras, tal aresta é factível?)

1. Nunca.
2. Sim, somente em fortalezas.
3. Sim, exceto em fortalezas.
4. Sim, tanto em fortalezas quanto em não-fortalezas.
5. NDA

Autor(a): Paulo Renato Nascimento