Enunciados:
Respostas:
1 - A questão pede que se ordene uma dada permutação usando apenas transposições. Entretanto, nem toda e qualquer série de transposições é aceitável, pois a resposta deve conter um número mínimo de operações. Dessa forma, a resposta deve conter uma justificativa que comprove que a série é mínima.
Em sala de aula foi obtida a seguinte resposta:
5 1 7 2 8 4 3 6 (Original)
5 1 2 7 8 4 3 6
5 1 2 4 3 6 7 8
1 2 4 3 5 6 7 8
1 2 3 4 5 6 7 8
Como a série de transposições possui quatro passos, d <= 4, onde d é a a distância de transposição.
Para justificar que a série obtida corresponde a um número mínimo de passos utiliza-se o limitante inferior obtido por Bafna e Pevzner 1998. Assim, criando o grafo direcionado com ciclos de arestas de cores alternadas da seqüência original temos:
Por esse grafo é possível verificar a existência de apenas um ciclo. Então, segundo Bafna e Pevzner 1998, temos o seguinte limitante inferior:
d >= (n + 1 - c)/2
d >= (8 + 1 - 1)/2
d >= 4
Onde c representa o número de ciclos e n número de elementos da permutação
Entretanto, já havíamos descoberto anteriormente que d <= 4.
4 <= d <= 4
d = 4
O que prova que a série de transposições encontrada em sala de aula é mínima.
2 - A questão dois é parecida com a primeira, diferenciando-se apenas pela permutação dada. Em sala de aula foi obtida a seguinte série de seis passos:
3 2 1 6 5 4 9 8 7 (original)
2 3 1 6 5 4 9 8 7
1 2 3 6 5 4 9 8 7
1 2 3 5 6 4 9 8 7
1 2 3 4 5 6 9 8 7
1 2 3 4 5 6 8 9 7
1 2 3 4 5 6 7 8 9
Como a série de transposições possui seis passos, d <= 6, onde d é a a distância de transposição.
A seqüência original gera o seguinte grafo.
O grafo possui 2 ciclos alternantes de tamanho 2 e 2 de tamanho 3. Dessa forma, calculando o limitante inferior:
d >= (n + 1 - codd)/2 = 8/2 = 4
Onde codd indica o número de ciclos ímpares.
Entretanto, a seqüência obtida em sala de aula possui 6 passos: 4 <= d <= 6. O que gera a dúvida se é um série mínima de transposições ou não. Dessa forma, foi deixado como desafio aos alunos encontrar a seqüência mínima de passos e justificar que ela é mínima. Caso a seqüência obtida em sala seja mínima, o desafio é provar esse fato.