Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/37333| Título: | O Jogo da Inundação em árvores |
| Título(s) alternativo(s): | Flood-it in trees |
| Autor(es): | Pereira, Bruno Henrique Silva |
| Orientador(es): | Almeida, Sheila Morais de |
| Palavras-chave: | Jogos de tabuleiro Algorítmos Árvores (Teoria dos grafos) Board games Algorithms Trees (Graph theory) |
| Data do documento: | 10-Fev-2025 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Ponta Grossa |
| Citação: | PEREIRA, Bruno Henrique Silva. O Jogo da Inundação em árvores. 2025. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação) - Universidade Tecnológica Federal do Paraná, 2025. |
| Resumo: | O presente trabalho aborda o problema do Jogo da Inundação aplicado a árvores, uma generalização de um jogo em tabuleiros coloridos, cujo objetivo é tornar o tabuleiro monocromático com o menor número possível de movimentos de inundação. Fleischer e Woeginger (2012) estabeleceram que a versão de decisão do Jogo de Inundação é um problema NP-Completo mesmo quando restrito a árvores. Além disso, Fleischer e Woeginger (2012) apresentaram um algoritmo de tempo polinomial para o Jogo da Inundação em grafos de intervalos. Considerando tais resultados, exploramos a classe dos grafos caterpillars, que são os grafos de intervalos que são árvores, e mostramos que o Jogo da Inundação tem solução algorítmica em tempo polinomial quando restrito a algumas árvores que não precisam ser grafos de intervalos mas têm propriedades estruturais especiais que permitem a redução do problema ao caso dos grafos de intervalos. A principal contribuição deste trabalho foi o desenvolvimento de um algoritmo de pré-processamento com complexidade polinomial, capaz de reduzir o Problema do Jogo da Inundação quando a entrada é uma destas árvores para o caso de um grafo de intervalos. Este algoritmo, tendo como entrada uma árvore colorida e enraizada, identifica subestruturas monocromáticas e produz árvores menores. Após o pré-processamento, as árvores são avaliadas quanto à possibilidade de serem tratadas como grafos de intervalos, permitindo a aplicação de algoritmos eficientes, como o proposto por Fleischer e Woeginger (2012). Os resultados apresentados abrem espaço para novas pesquisas, como a aplicação desta abordagem em outras subclasses de árvores ou em variações do problema, como jogos de inundação com pivôs móveis ou em grafos com diferentes restrições cromáticas. |
| Abstract: | The present work addresses the problem of the Flood-It Game applied to trees, a generalization of a game played on colored grids, where the objective is to make the grid monochromatic with the fewest number of flooding moves. Fleischer e Woeginger (2012) established that the decision version of the Flood-It Game is an NP-Complete problem, even when restricted to trees. Moreover, Fleischer e Woeginger (2012) presented a polynomial-time algorithm for the Flood-it Game on interval graphs. Considering such results, we explore the class of caterpillar graphs, which are interval graphs that are also trees, and show that the Flood-It Game has a polynomial-time algorithmic solution when restricted to certain trees. While these trees are not necessarily interval graphs, they possess special structural properties that allow the reduction of the problem to the case of interval graphs. The main contribution of this work is the development of a polynomial-time preprocessing algorithm that reduces the Flood-It Game on such trees to the case of interval graphs. This algorithm takes a colored rooted tree as input, identifies monochromatic substructures, and outputs smaller trees. After preprocessing, the trees are evaluated for compatibility as interval graphs, enabling the application of efficient algorithms, such as the one proposed by Fleischer e Woeginger (2012). The results presented pave the way for further research, such as applying this approach to other subclasses of trees or variations of the problem, including free pivots or graphs with different chromatic constraints. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/37333 |
| Aparece nas coleções: | PG - Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| jogoinundacaoarvores.pdf | 719,38 kB | Adobe PDF |  Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
