Conjunto independente: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
esboço específico |
|||
Linha 22: | Linha 22: | ||
==Ver== |
==Ver== |
||
*[[Teoria dos grafos]] |
*[[Teoria dos grafos]] |
||
{{esboço}} |
{{esboço-teoria}} |
||
[[Categoria:Teoria dos grafos]] |
[[Categoria:Teoria dos grafos]] |
Revisão das 20h10min de 2 de março de 2009
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ção
é Conjunto independente de
Caracteristicas
As seguintes indicações são equivalentes:
- é um conjunto independente de
- é uma cobertura de vertices de
- é um conjunto independente de