DAA - Max Cliques
Em um gráfico não direcionado, um cliqueé um subgráfico completo do gráfico fornecido. Sub-gráfico completo significa que todos os vértices deste sub-gráfico estão conectados a todos os outros vértices deste sub-gráfico.
O problema Max-Clique é o problema computacional de encontrar o clique máximo do grafo. Max clique é usado em muitos problemas do mundo real.
Vamos considerar um aplicativo de rede social, onde os vértices representam o perfil das pessoas e as arestas representam o conhecimento mútuo em um gráfico. Neste gráfico, um clique representa um subconjunto de pessoas que se conhecem.
Para encontrar um clique máximo, pode-se inspecionar sistematicamente todos os subconjuntos, mas esse tipo de busca de força bruta consome muito tempo para redes que compreendem mais do que algumas dezenas de vértices.
Algorithm: Max-Clique (G, n, k)
S := Φ
for i = 1 to k do
t := choice (1…n)
if t Є S then
return failure
S := S ∪ t
for all pairs (i, j) such that i Є S and j Є S and i ≠ j do
if (i, j) is not a edge of the graph then
return failure
return successAnálise
O problema da Max-Clique é um algoritmo não determinístico. Neste algoritmo, primeiro tentamos determinar um conjunto dek vértices distintos e então tentamos testar se esses vértices formam um gráfico completo.
Não existe um algoritmo determinístico de tempo polinomial para resolver este problema. Este problema é NP-Completo.
Exemplo
Dê uma olhada no gráfico a seguir. Aqui, o subgráfico contendo os vértices 2, 3, 4 e 6 forma um gráfico completo. Portanto, este subgráfico é umclique. Como este é o subgráfico máximo completo do gráfico fornecido, é um4-Clique.
