MO640 - Questão para a prova oral
Número: 036
Enunciado:
Quanto à ordenação por reversão podemos afirmar que:
- 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.
- 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.
- 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.
- Um componente ruim é um obstáculo se, e somente se, ele
não separa quaisquer 2 outros componentes bons.
- NDA
Autor(a): Paulo Renato de Faria