| Resumo : |
Um clique de um grafo é um conjunto de vértices que são mutuamente adjacentes. O objetivo deste trabalho é abordar aspectos teóricos e práticos da determinação de cliques maximais em grafos. Para isto, é apresentada uma formalização dos problemas Completos em NP, baseando-se na interpretação de problemas como linguagens formais e concluindo que o problema em questão pertence àquela classe; foi feita uma abordagem teórica sobre cliques em grafos, apresentando os teoremas mais fundamentais deste assunto; e, ainda, uma apresentação de algoritmos baseados em heurísticas de determinação de cliques maximais em grafos, seguida de testes e análises dos mesmos.
|