Resolvido: Algoritmos - Teoria e Prática - 3ª Ed. 2012 | Cap 34.5 Ex 1E
51
Algoritmos - Teoria e Prática - 3ª Ed. 2012

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas Cormen IBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 5keyboard_arrow_downkeyboard_arrow_up

Sabendo que o problema de isomorfismo de subgrafos toma dois grafos não dirigidos e e pergunta se é isomorfo a algum subgrafo de . Vamos mostrar que esse problema é NP-Completo.

Passo 2 de 5keyboard_arrow_downkeyboard_arrow_up

Para resolver esse problema, primeiro perceba que ele está no conjunto dos NP, já que há injeção de em , de modo que é isomorfo de sua imagem.

Passo 3 de 5keyboard_arrow_downkeyboard_arrow_up

Agora para entender sua completeza, faremos uma redução ao problema do clique. Isto é, para saber se um grafo tem um clique de tamanho k, simplesmente faça de um grafo completo de k vértices e mantenha .

Passo 4 de 5keyboard_arrow_downkeyboard_arrow_up

Resolver o problema de isomorfismo de subgrafos de forma eficiente permitiria a solução do problema do clique de forma eficiente, o que não ocorre. Temos, portanto, que o problema de isomorfismo de subgrafos é NP completo.

Passo 5 de 5keyboard_arrow_downkeyboard_arrow_up

Concluímos, portanto, usando redução do problema do clique, que o problema de isomorfismo de subgrafos é NP completo.

Navegar por capítulo

Aprenda agora com os exercícios mais difíceis

R$29,90/mês

Assine o PremiumCancele quando quiser, sem multa

Aproveite também

  • check Todos os materiais compartilhados
  • check Biblioteca com 5.000 livros, escolha 5 por mês
  • check Videoaulas exclusivas
  • check Resumos por tópicos