Use este identificador para citar ou linkar para este item:
http://repositorio.ufc.br/handle/riufc/49758| Tipo: | TCC |
| Título: | Obtendo o número de Grundy de grades parciais |
| Autor(es): | Pinho, Bruno da Silva |
| Orientador: | Araruna, Arthur Rodrigues |
| Coorientador: | Silva, Anderson Lemos da |
| Palavras-chave: | Teoria dos Grafos;Coloração de grafos;Algoritmos |
| Data do documento: | 2019 |
| Citação: | PINHO, Bruno da Silva. Obtendo o número de Grundy de grades parciais. 2019. 50 f. Trabalho de Conclusão de Curso (Graduação em Sistemas de Informação)- Universidade Federal do Ceará, Campus de Quixadá, Quixadá, 2019. |
| Resumo: | O número de Grundy é a maior quantidades de cores que o algoritmo guloso de coloração consegue atribuir a um grafo. Para grafos em geral é difícil de se obter esse número. Então, neste trabalho, trabalhamos sobre uma classe de grafos denominada de grades parciais que, são subgrafos de grades, e descrevemos uma forma de obter o número de Grundy para essa classe. Neste trabalho também mostramos propriedades e estruturas que nos permitem construir uma solução algorítmica para esses tipos de grafos. Em específico, apresentamos duas soluções que podem ser utilizadas para encontrar o número de Grundy de grades parciais. |
| Abstract: | The Grundy number is the larger amoust of colors that the greedy coloring algorithm can assign to a graph. For graphs in general, this number is difficult to obtain. In this work we presented a class of graphs called partial grids, which are subgraphs of grids, and a way to determine the Grundy Number for this class. We also show properties and structures that allow to build an algorithmic solution for these types of graphs. Specifically, we present two solutions taht can be used to determine the Grundy Number of partial grids. |
| URI: | http://www.repositorio.ufc.br/handle/riufc/49758 |
| Aparece nas coleções: | SISTEMAS DE INFORMAÇÃO - QUIXADÁ - TCC |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| 2019_tcc_bdaspinho.pdf | 1,18 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.