Abrir menu principal

Alterações

6 bytes removidos, 18h04min de 23 de setembro de 2008
m
Checkwiki: limpeza de formata��o, typos fixed: indepedente → independente utilizando AWB
[[Imagem:Independent_set_graphIndependent set graph.gif|thumb|Um conjunto independente num grafo.]]
Na [[teoria dos grafos]], um '''conjunto independente''' de um grafo <math>G</math> é um conjunto <math>S</math> de vértices de <math>G</math> tal que não existem dois vértices adjacentes contidos em S. Em outras palavras, se <math>a</math> e <math>b</math> são vértices quaisquer de um conjunto independente, não há aresta entre <math>a</math> e <math>b</math>.<br />
 
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 indepedenteindependente 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===
 
* <math>\forall V^{\prime\prime} \sub V^\prime : V^{\prime\prime}</math> é um ''conjunto independente'' de <math>G</math>
 
 
==Ver==
{{esboço}}
 
[[categoriaCategoria:Teoria dos grafos]]
 
[[cs:Nezávislá množina]]
49 454

edições