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 numero de obstáculos é ímpar

Z- Não tenho componentes boas e o numero 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 pode mos 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