Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/49758| Type: | TCC |
| Title: | Obtendo o número de Grundy de grades parciais |
| Authors: | Pinho, Bruno da Silva |
| Advisor: | Araruna, Arthur Rodrigues |
| Co-advisor: | Silva, Anderson Lemos da |
| Keywords: | Teoria dos Grafos;Coloração de grafos;Algoritmos |
| Issue Date: | 2019 |
| Citation: | 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. |
| Abstract in Brazilian Portuguese: | 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 |
| Appears in Collections: | SISTEMAS DE INFORMAÇÃO - QUIXADÁ - TCC |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2019_tcc_bdaspinho.pdf | 1,18 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.