Conjunto independente
Origem: Wikipédia, a enciclopédia livre.
Na teoria dos grafos, um conjunto independente de um grafo G é um conjunto S de vértices de G tal que não existem dois vértices adjacentes contidos em S. Em outras palavras, se a e b são vértices quaisquer de um conjunto independente, não há aresta entre a e b.
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 indepedente 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.
[editar] Definição
é Conjunto independente de 
[editar] Caracteristicas
As seguintes indicações são equivalentes:
- é Conjunto independente de G
é Vertex Cover de G
é Conjunto independente de G
