Olá, hoje vamos comemorar a estreia do Brasil na copa resolvendo mais problemas de maratona! Todos conhecem o jogo de dominós, em que peças com dois valores devem ser colocadas na mesa em sequência, de tal forma que os valores de peças imediatamente vizinhas sejam iguais. O objetivo do problema 1331. Dominó é justamente esse: determinar se é possível formar uma sequência com todas as peças de dominó fornecidas.
Modelagem
Antes de resolver esse problema, irei fazer uma breve revisão sobre grafos. Falarei apenas do necessário para solucionar esse problema. Se você não sabe o que são grafos, eu sugiro fortemente que você estude um pouco sobre isso já que eles são uma ferramenta muito poderosa na resolução de problemas.
Em teoria de grafos, diz-se que um grafo possui um caminho euleriano se existe um caminho que visita cada aresta apenas uma vez. Com caso especial, um circuito Euleriano é um caminho Euleriano que começa e termina no mesmo vértice. O conceito foi introduzido por Leonard Euler para a resolução do famoso problema das sete pontes de Königsberg.
Em um grafo euleriano G todos os vértices têm grau par.
Prova: Seja G um grafo euleriano. Logo, por definição, ele contém um circuito euleriano. Assim, por cada vértice desse circuito, existe uma aresta que chega nesse vértice e outra que sai desse vértice. Como toda aresta faz parte do caminho, isto é, nenhuma aresta fica fora do caminho, necessariamente o número de arestas que passam por cada vértice é par.
Se removermos uma aresta de um grafo euleriano, ele deixara de ser euleriano, mas ainda conterá um caminho euleriano (é só começar e terminar o caminho nos vértices correspondentes as arestas removidas). Isso significa que um grafo que contém um caminho euleriano pode ter dois vértices de grau ímpar.
Voltando aos dominós, ligar peças, montar caminhos, é um forte indicio de que nosso problema pode ser resolvido usando-se grafos. Seja o seguinte grafo: G, onde os vértices são os números 0..6 e as arestas são os dominós. Será possível montar uma sequência com todos os dominós se, e somente se, G contiver um caminho euleriano. Em outras palavras, uma sequência de dominós não é nada mais do que um caminho euleriano onde eu peguei as arestas do grafo (os dominós) e enfileirei.
Note que os dominós podem formar um grafo que não é conexo, mas que possui dois sub grafos conexos e eulerianos, assim é necessário testar isso (com uma busca em profundidade por exemplo) para garantir que os dominós formem uma sequência única.
Nenhum comentário:
Postar um comentário