46

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

Thomas Cormen IBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 4keyboard_arrow_downkeyboard_arrow_up

Nesse exercício temos que um conjunto independente de um grafo G = (V, E) é um subconjunto de vértices, tal que cada aresta em E é incidente em no máximo um vértice em V’.

O exercício é dividido em quatro itens, no primeiro temos que formular um problema de decisão relacionado para o problema do conjunto independente e provar que ele é NP-completo.

Passo 2 de 4keyboard_arrow_downkeyboard_arrow_up

O problema do conjunto independente é um exemplo de um problema de otimização, o qual procura encontrar o maior ou máximo conjunto de vértices que não são adjacentes aos outros.

É possível transformar ou converter um problema de conjunto independente em um problema de decisão para facilitar a geração do tipo uniforme de saídas (Sim ou Não).

Passo 3 de 4keyboard_arrow_downkeyboard_arrow_up

Um problema de conjunto independente pode ser formulado como um problema de decisão da seguinte maneira.

Entrada: é dado um grafo G com V vértices, E arestas e um limite inferior ou um inteiro N.

Pergunta: Um grafo G contém um inteiro N, de modo que exista ao menos um conjunto P de não adjacentes ou um conjunto independente de vértices de cardinalidade ou tamanho máximo N?

Saída: Sim, existe um conjunto independente P de vértices do tamanho de quase N.

Passo 4 de 4keyboard_arrow_downkeyboard_arrow_up

Agora vamos provar que o conjunto é NP-completo. Veja abaixo.

Dado um conjunto independente S de um grafo não direto, ele é NP-completo se existir um algoritmo de tempo polinomial pegando um objeto do problema. A complexidade do tempo de processo desse algoritmo é , o qual é simplesmente o tempo polinomial e, portanto, pode ser constatado que S pertence a NP-completo.

Navegar por capítulo

Aprenda agora com os exercícios mais difíceis

R$29,90/mês

Cancele quando quiser, sem multa

Aproveite também

  • check Todos os materiais compartilhados
  • check Biblioteca com mais de 5.000 livros
  • check Videoaulas exclusivas
  • check Resumos por tópicos