24

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

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

ALUNOS QUE TAMBÉM VISUALIZARAM

  • +6.285

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.

Depoimentos de estudantes que já assinaram o Exercícios Resolvidos

Nathalia Nascimento fez um comentárioCEFET/RJ • Engenharia
Foi um apoio àquelas aulas que não acabam totalmente com as dúvidas ou mesmo naquele momento de aprender o conteúdo sozinha. Além disso, dispensou a necessidade de um orientador e por isso, permitiu que eu estudasse em qualquer local e hora.
Valdivam Cardozo fez um comentárioUFRB • Engenharia
Tive uma sensação maior de autonomia nos estudos, as vezes era frustante não conseguir resolver uma determinada questão e nem sempre os professores corrigem as listas que passam.