036-2007

MO640 - Questão para a prova oral
Número: 036
Enunciado:
Quanto à ordenação por reversão podemos afirmar que:

1. Um componente B separa os componentes A e C se todas as cordas no diagrama Realidade-Desejo que ligam um vértice em A a um vértice em C cruzam uma aresta desejo de B. Neste caso, a reversão usando uma aresta realidade de A e outra aresta realidade de C torna B um bom componente, mas decrementa o número de ciclos em 1.
2. Assumindo o desenho em forma de circunferência do Diagrama Realidade-Desejo, dois ciclos se entrelaçam se, e somente se, a aresta desejo de um ciclo cruza a aresta realidade do outro ciclo.
3. Um ciclo é bom se, e somente se, ele tem 2 arestas realidade que divergem. Neste caso, existe uma reversão que aplicada sobre este ciclo diminui em 1 o número de ciclos no diagrama Realidade-Desejo.
4. Um componente ruim é um obstáculo se, e somente se, ele não separa quaisquer 2 outros componentes bons.
5. NDA

Autor(a): Paulo Renato de Faria