MODELOS MATEMÁTICOS E HEURÍSTICA PARA O NÚMERO DE ENVOLTÓRIA DE UM GRAFO NAS CONVEXIDADES P3 E P3*
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
Licença
Autores que publicam nesta revista concordam com os seguintes termos:
a. Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Creative Commons Attribution License que permitindo o compartilhamento do trabalho com reconhecimento da autoria do trabalho e publicação inicial nesta revista.
b. Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
c. Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado.