Abrir menu principal
Question book.svg
Este artigo ou secção não cita fontes confiáveis e independentes (desde agosto de 2010). Ajude a inserir referências.
O conteúdo não verificável pode ser removido.—Encontre fontes: Google (notícias, livros e acadêmico)
Os nove vértices azuis formam um conjunto independente do grafo acima.

Na teoria dos grafos, um conjunto independente de um grafo é um conjunto de vértices de tal que não existem dois vértices adjacentes contidos em S. Em outras palavras, se e são vértices quaisquer de um conjunto independente, não há aresta entre e .

Todo grafo tem ao menos um conjunto independente: o conjunto vazio. Um grafo pode ter vários conjuntos independentes distintos.

Se S é um conjunto independente de G e não existe um conjunto independente de G maior que S, diz-se que S é um conjunto independente máximo de G. O problema de, dado um grafo G, determinar se há um conjunto independente de tamanho k é um problema NP-completo.

DefiniçãoEditar

  é Conjunto independente de  

CaracterísticasEditar

As seguintes indicações são equivalentes:

  •   é um conjunto independente de  
  •   é uma cobertura de vertices de  
  •   é um conjunto independente de  

VerEditar

  Este artigo sobre uma Teoria é um esboço. Você pode ajudar a Wikipédia expandindo-o.