Conjunto independente

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde agosto de 2010).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.
Um conjunto independente num grafo.

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 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[editar | editar código-fonte]

V^\prime é Conjunto independente de G \Longleftrightarrow \forall u,v \in V^\prime: u \not= v \Rightarrow \left( u,v \right) \notin E

Características[editar | editar código-fonte]

As seguintes indicações são equivalentes:

Ver[editar | editar código-fonte]

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