048-2006

MO640 - Questão para a prova oral
Número: 048
Enunciado: Dados
Condições:
X- Tenho uma componente boa no grafo
Y- Não tenho componentes boas e o número de obstáculos é ímpar
Z- Não tenho componentes boas e o número de obstáculos é par
Tipo de Reversões:
Tipo 1: Reversão segura do tipo “quebra ciclos” que não cria componentes ruins.
Tipo 2: Mescla dois obstáculos opostos.
Tipo 3: “Quebra” um obstáculo, agindo em um ciclo ruim e tornando-o um ciclo bom.
Considerando o algoritmo de ordenar uma permutação usando reversões apresentado nas “Lectures” de Saad Mneimneh podemos dizer que:

1. Se X então aplica Tipo 1. Se Y então aplica Tipo 2. Se Z então aplica Tipo 3.
2. Se X então aplica Tipo 1. Se Y então aplica Tipo 3. Se Z então aplica Tipo 2.
3. Se X então aplica Tipo 3. Se Y então aplica Tipo 1. Se Z então aplica Tipo 2.
4. Se X então aplica Tipo 3. Se Y então aplica Tipo 2. Se Z então aplica Tipo 1.
5. NDA

Autor(a): Mirela Dal Col Silva