Ciclo Hamiltoniano em Grafos de Rearranjo de Genomas por Transposições Pré-Fixadas

Uma transposição é uma operação que troca dois blocos consecutivos e adjacentes em uma permutação. Uma transposição pré-fixada é uma transposição que move o primeiro elemento em uma permutação. Definimos um grafo denominado Grafo de Rearranjo de Genomas por Transposições Pré-fixadas no qual cada vértice está associado a uma permutação do Grupo Simétrico quando existe uma transposição pré-fixada que aplicada a uma permutação produz a outra.

Neste trabalho apresentamos propriedades deste grafo, dentre as quais a principal é a existência e a construção de ciclos Hamiltonianos. Além de ser interessante pelo fato de o problema de saber se existe ciclo Hamiltoniano em um grafo ser NPCompleto, também corrobora a conjectura de Lovász sobre ciclo Hamiltoniano em Grafos de Cayley. Em uma abordagem de Bioinformática, também torna possível listar todas as permutações de um determinado tamanho, numa ordem na qual há uma transposição pré-fixada entre duas permutações consecutivas, e ainda de modo que todas as permutações com o mesmo último elemento estejam consecutivas nesta listagem, o que auxilia no estudo do problema desafiador de ordenar por transposições.