Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2018-10-30T11:09:54Z
No. of bitstreams: 2
Dissertação - Braully Rocha da Silva - 2018.pdf: 1396149 bytes, checksum: 9a9145cb07e037a784d2d15d43cbd1ff (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-10-30T11:20:36Z (GMT) No. of bitstreams: 2
Dissertação - Braully Rocha da Silva - 2018.pdf: 1396149 bytes, checksum: 9a9145cb07e037a784d2d15d43cbd1ff (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-10-30T11:20:36Z (GMT). No. of bitstreams: 2
Dissertação - Braully Rocha da Silva - 2018.pdf: 1396149 bytes, checksum: 9a9145cb07e037a784d2d15d43cbd1ff (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2018-09-24 / Outro / In this work we present results and implementantions for hull and Carathéodory numbers in P3 convexity. We obtain results for graphs of diameter 2 having cut-vertex for both problems. Finally, entering more complex cases, we were able to determine a logarithmic limit, means of algorithm, for the hull number in case of graph diameter 2 and 2-connected. Exploring more restrictive cases, we determined a constant limit for some subclasses of graphs of diameter 2. We made also implementations and algorithms for these parameters. Implementations algorithms heuristic, parallel, and brute force. Finally, although not directly related, we developed an algorithm for Moore's graphs generation, which may be one of the ways to find Moore missinge graph, if it exists, a question that remains unknown for 55 years. And finally, we conclude with some conjectures interesting, for limits to the hull and Carathéodory numbers, in other classes of graphs, that were not explored in this work, but was identified by the implementations, and can be better explored in future works. / Nesta dissertação, tratamos de limites para o número envoltório e o número de Carathéodory na Convexidade P3. Aferimos resultados para grafos de diâmetro 2 com vértice de corte para ambos os problemas. Adentrando em casos mais complexos, conseguimos determinar um limite logarítmico, por meio de algoritmo pseudo-polimonial, para o número envoltório de grafos de diâmetro 2 biconexos. Explorando um pouco mais restritivamente, conseguimos determinar um limite constante para algumas subclasses de grafos de diâmetro 2, os grafos maximais sem triângulo. Não atendo somente aos resultados teóricos, realizamos também implementações e algoritmos para esses parâmetros. As implementações perfazem algoritmos heurísticos, paralelos e força bruta. Por fim, embora não diretamente relacionado, desenvolvemos uma algoritmo para geração de grafos de Moore, que pode ser um dos caminhos para encontrar o ultimo grafo de Moore, caso ele exista. Questão que remanesce desconhecido e procurada por 55 anos.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/9008 |
| Date | 24 September 2018 |
| Creators | Silva, Braully Rocha da |
| Contributors | Coelho, Erika Morais Martins, Silva, Hebert Coelho da, Coelho, Erika Morais Martins, Silva, Hebert Coelho da, Santana, Márcia Rodrigues Cappelle, Souza, Uéverton dos Santos |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 3671711205811204509, 2442915598251853972 |
Page generated in 0.0028 seconds