Para responder esta questão, temos que, primeiramente, entender alguns conceitos que são descritos por Saad Mneimneh em Computational Biology Lecture 16: Genome rearrangements, sorting by reversals, como segue:
-Um ciclo só é bom se, e somente se, pelo menos duas de suas bordas de realidade são divergentes. Um ciclo é ruim, se todas as suas bordas de realidade são convergentes;
-Um componente é bom, se pelo menos um de seus ciclos é bom. Um componente é ruim se todos os seus ciclos são ruins;
-Um componente ruim pode tornar-se um obstáculo se, e somente se, ele não isolar nenhum componente ruim dos demais componentes ruins;
-Um obstáculo é considerado um super obstáculo se a sua remoção pode transformar um componente que não é um obstáculo em um obstáculo;
-Uma permutação α só será chamada de fortaleza, se, e somente se, o RD(α) possuir um número ímpar, maior que um, de super obstáculos.
Para α ser chamada de fortaleza deve conter, pelo menos, três componentes obstáculos sendo isolados por um não obstáculo. Como precisamos encontrar o número mínimo de ciclos de uma fortaleza, consideramos que um componente ruim será formado por um único ciclo ruim.
Criamos um grafo colocando três componentes A, B e C, compostos por apenas um ciclo ruim cada, dispostos de forma que não isolam ninguém, tornando-os obstáculos. Adicionamos mais um componente D, formado por um único ciclo ruim isolando A, B e C completamente uns dos outros. D, embora seja um componente ruim, não é um obstáculo pois isola os outros componentes ruins uns dos outros. Removendo-se qualquer um dos componentes obstáculos A, B ou C, não conseguimos fazer com que D, que é o único não-obstáculo do grafo, torne-se um obstáculo, pois continua isolando os outros dois componentes obstáculos remanescentes. Então, A, B e C não são considerados super obstáculos, não atendendo o critério de fortaleza. A permutação utilizada para a verificação desta situação foi α=(-10, +11, -9, -4, -2, -3, -1, -8, -6, +7, -5).
Um segundo grafo foi criado mantendo-se os componentes A, B e C, e adicionando-se mais um componente E ruim à permutação. E foi colocado de forma a isolar A e B um do outro e dos demais, portanto não sendo um obstáculo, e D continuou isolando C. Removendo-se A ou B, E continua não sendo um obstáculo pois ainda estará isolando o componente remanescente dos demais, não podendo então, A e B, serem super obstáculos. No entanto, removendo-se C, D passa a ser um obstáculo, mostrando que apenas C é um super obstáculo, não podendo α ser chamado de fortaleza. A permutação utilizada para a verificação da segunda situação foi α=(-13, -14, -12, -7, -5, -3, -4, -2, +6, -1, -11, -9, -10, -8).
Finalmente, adicionamos mais um componente F composto por um único ciclo ruim sendo que A, B e C, são isolados respectivamente por D, E e F. A, B e C continuaram sendo obstáculos não isolando nenhum componente e D, E e F, não são obstáculos pois isolam A, B e C dos demais. Ao removermos qualquer um dos componentes obstáculos A, B ou C, tornamos o componente que o isola dos demais, em obstáculo, pois este passa a não isolar mais ninguém. Logo, cada um dos obstáculos A, B e C são considerados super obstáculos, satisfazendo a condição de fortaleza. A permutação utilizada para a verificação da terceira situação foi α=(-16, -14, +15, -13, +17, -12, -10, -8, -9, -7, -11, -6, -4, -2, -3, -1, -5).
O número mínimo então de ciclos que foram necessários chamar α de fortaleza foi seis, sendo a alternativa correta para esta questão a de número 2.
Comentário interessante, mas precisa de algumas correções.
Em primeiro lugar, não são "bordas" realidade; são "arestas" realidade.
Na definição de obstáculo, você diz que ele deve isolar um dos outros. Não é bem assim, ele tem que separar 2. Se ele deixar, digamos, 5 de uma lado e 6 de outro, já separa.
Sua definição de fortaleza precisa de ajuste. Não é ter um número ímpar, maior que um, de super-obstáculos. É ter um número ímpar de obstáculos, e todos serem super-obstáculos. Observe a diferença. Pela sua definição, uma permutação que tivesse 3 soper-obstáculos e mais 2 obstáculos simples seria uma fortaleza, o que está errado.
Por fim, todos os seus exemplos de alpha estão errados. Eu fiz os diagramas e não correspondem ao que você descreve.
Para responder esta questão, temos que, primeiramente, entender alguns conceitos que são descritos por Saad Mneimneh em Computational Biology Lecture 16: Genome rearrangements, sorting by reversals, como segue:
ResponderExcluir-Um ciclo só é bom se, e somente se, pelo menos duas de suas bordas de realidade são divergentes. Um ciclo é ruim, se todas as suas bordas de realidade são convergentes;
-Um componente é bom, se pelo menos um de seus ciclos é bom. Um componente é ruim se todos os seus ciclos são ruins;
-Um componente ruim pode tornar-se um obstáculo se, e somente se, ele não isolar nenhum componente ruim dos demais componentes ruins;
-Um obstáculo é considerado um super obstáculo se a sua remoção pode transformar um componente que não é um obstáculo em um obstáculo;
-Uma permutação α só será chamada de fortaleza, se, e somente se, o RD(α) possuir um número ímpar, maior que um, de super obstáculos.
Para α ser chamada de fortaleza deve conter, pelo menos, três componentes obstáculos sendo isolados por um não obstáculo. Como precisamos encontrar o número mínimo de ciclos de uma fortaleza, consideramos que um componente ruim será formado por um único ciclo ruim.
Criamos um grafo colocando três componentes A, B e C, compostos por apenas um ciclo ruim cada, dispostos de forma que não isolam ninguém, tornando-os obstáculos. Adicionamos mais um componente D, formado por um único ciclo ruim isolando A, B e C completamente uns dos outros. D, embora seja um componente ruim, não é um obstáculo pois isola os outros componentes ruins uns dos outros. Removendo-se qualquer um dos componentes obstáculos A, B ou C, não conseguimos fazer com que D, que é o único não-obstáculo do grafo, torne-se um obstáculo, pois continua isolando os outros dois componentes obstáculos remanescentes. Então, A, B e C não são considerados super obstáculos, não atendendo o critério de fortaleza. A permutação utilizada para a verificação desta situação foi α=(-10, +11, -9, -4, -2, -3, -1, -8, -6, +7, -5).
Um segundo grafo foi criado mantendo-se os componentes A, B e C, e adicionando-se mais um componente E ruim à permutação. E foi colocado de forma a isolar A e B um do outro e dos demais, portanto não sendo um obstáculo, e D continuou isolando C. Removendo-se A ou B, E continua não sendo um obstáculo pois ainda estará isolando o componente remanescente dos demais, não podendo então, A e B, serem super obstáculos. No entanto, removendo-se C, D passa a ser um obstáculo, mostrando que apenas C é um super obstáculo, não podendo α ser chamado de fortaleza. A permutação utilizada para a verificação da segunda situação foi α=(-13, -14, -12, -7, -5, -3, -4, -2, +6, -1, -11, -9, -10, -8).
Finalmente, adicionamos mais um componente F composto por um único ciclo ruim sendo que A, B e C, são isolados respectivamente por D, E e F. A, B e C continuaram sendo obstáculos não isolando nenhum componente e D, E e F, não são obstáculos pois isolam A, B e C dos demais. Ao removermos qualquer um dos componentes obstáculos A, B ou C, tornamos o componente que o isola dos demais, em obstáculo, pois este passa a não isolar mais ninguém. Logo, cada um dos obstáculos A, B e C são considerados super obstáculos, satisfazendo a condição de fortaleza. A permutação utilizada para a verificação da terceira situação foi α=(-16, -14, +15, -13, +17, -12, -10, -8, -9, -7, -11, -6, -4, -2, -3, -1, -5).
O número mínimo então de ciclos que foram necessários chamar α de fortaleza foi seis, sendo a alternativa correta para esta questão a de número 2.
Caro Alex,
ResponderExcluirComentário interessante, mas precisa de algumas correções.
Em primeiro lugar, não são "bordas" realidade; são "arestas" realidade.
Na definição de obstáculo, você diz que ele deve isolar um dos outros. Não é bem assim, ele tem que separar 2. Se ele deixar, digamos, 5 de uma lado e 6 de outro, já separa.
Sua definição de fortaleza precisa de ajuste. Não é ter um número ímpar, maior que um, de super-obstáculos. É ter um número ímpar de obstáculos, e todos serem super-obstáculos. Observe a diferença. Pela sua definição, uma permutação que tivesse 3 soper-obstáculos e mais 2 obstáculos simples seria uma fortaleza, o que está errado.
Por fim, todos os seus exemplos de alpha estão errados. Eu fiz os diagramas e não correspondem ao que você descreve.
Nota 4,5 (quatro e meio)