MODELOS MATEMÁTICOS E HEURÍSTICA PARA O NÚMERO DE ENVOLTÓRIA DE UM GRAFO NAS CONVEXIDADES P3 E P3*

Autores

  • Gabriel Hellen de Sousa
  • JÚLIO CÉSAR SILVA ARAÚJO
  • Manoel Bezerra Campelo Neto

Resumo

O número de envoltória (hull number) de um grafo G = (V,E) não-orientado, onde V é 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 estudados neste trabalho foram P3 e P3*, onde, dados dois vértices contaminados v1,v2 pertencentes a V, todos aqueles que são vizinhos simultâneos de v1 e v2 estarão contaminados na próxima iteração em P3, e só serão contaminados em P3* se esses vizinhos não definirem a aresta (v1,v2) em E. 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 dois modelos matemáticos e uma heurística para o problema. Para resolução dos modelos utilizou-se o solver 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. O primeiro modelo, denominado passo-de-contaminação, mostrou-se mais lento, computacionalmente, que o segundo, chamado co-convexo, na maior parte dos testes. A heurística apresentou um ótimo desempenho, encontrando a solução ótima na maioria dos testes.Como trabalho futuro, serão testadas uma maior quantidade de instâncias e uma maior variação da densidade dos grafos. Também pretendemos aprimorar o modelo passo de contaminação com o uso de propriedades especı́ficas para gerar restrições que fortaleçam a formulação.

Publicado

2019-01-14

Edição

Seção

XXXVII Encontro de Iniciação Científica