Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/42201| Type: | TCC |
| Title: | Uma abordagem de programação matemática para o número de envoltória de um grafo |
| Title in English: | A Mathematical programming approach to the envelope number of a graph |
| Authors: | Sousa, Gabriel Hellen de |
| Advisor: | Campêlo Neto, Manoel Bezerra |
| Co-advisor: | Araújo, Júlio César Silva |
| Keywords: | Convexidade;Número de Envoltória;Heurística;Convexity;Hull number;Heuristic |
| Issue Date: | 2018 |
| Citation: | 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. |
| Abstract in Brazilian Portuguese: | 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 |
| Appears in Collections: | MATEMÁTICA INDUSTRIAL - Monografias |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2018_tcc_ghsousa.pdf | 545,71 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.