Por favor, use este identificador para citar o enlazar este ítem:
http://repositorio.ufc.br/handle/riufc/42201| Tipo: | TCC |
| Título : | Uma abordagem de programação matemática para o número de envoltória de um grafo |
| Título en inglés: | A Mathematical programming approach to the envelope number of a graph |
| Autor : | Sousa, Gabriel Hellen de |
| Tutor: | Campêlo Neto, Manoel Bezerra |
| Co-asesor: | Araújo, Júlio César Silva |
| Palabras clave : | Convexidade;Número de Envoltória;Heurística;Convexity;Hull number;Heuristic |
| Fecha de publicación : | 2018 |
| Citación : | SOUSA, Gabriel Hellen de. Uma abordagem de programação matemática para o número de envoltória de um grafo. 58 f. 2018. Trabalho de Conclusão de Curso (graduação em Matemática Industrial) – Universidade Federal do Ceará, Centro de Ciências, , Fortaleza, 2018. |
| Resumen en portugués brasileño: | O número de envoltória (hull number) de um grafo G = (V;E) não-orientado, ondeV é o conjunto de vértices e E, o conjunto de arestas, consiste no menor número de vértices que, inicialmente contaminados, conseguem, iterativamente, contaminar todo o grafo. Os tipos de contaminação (convexidade) estudados neste trabalho foram geodésica, P3 e P3∗. Determinar o número de envoltória é um problema NP-Difícil, mesmo para classes de grafos como bipartidos. Neste trabalho, foram estudados e implementados modelos matemáticos e heurísticas para o problema. Para resolução dos modelos utilizou-se o CPLEX, acoplado à linguagem de programação C++, e para a heurística utilizou-se uma implementação na mesma linguagem. Os grafos usados como instâncias de teste foram bipartidos e arbitrários, criados a partir de dois parâmetros: quantidade de vértices e um fator de probabilidade para definir a existência das arestas. Os resultados apresentados por cada modelo e pela heurística, referentes ao tempo de execução e à solução, foram armazenados e comparados. |
| Abstract: | The hull number of an undirected graph G = (V;E), where V is the set of vertices and E is the set of edges, consists of the smallest number of vertices that, initially contaminated, can iteratively contaminate the whole graph. The types of contamination (convexity) studied in this work were geodetic, P3, and P3∗. Determining the hull number is an NP-hard problem, even for bipartite graphs. In this work, mathematical models and heuristics for the problem were studied and implemented. To solve the models, the CPLEX was used, coupled with the C ++ programming. The same language was used to code the heuristic. The graphs used as test instances were bipartite and arbitrary graphs, created from two parameters: the number of vertices and a probability factor to define the existence of edges. The results presented by each model and the heuristic, related to the execution time and solution quality, were stored and compared. |
| URI : | http://www.repositorio.ufc.br/handle/riufc/42201 |
| Aparece en las colecciones: | MATEMÁTICA INDUSTRIAL - Monografias |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 2018_tcc_ghsousa.pdf | 545,71 kB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.