Conjunto independente: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m XHTML-syntax |
|||
| Linha 1: | Linha 1: | ||
[[Imagem: |
[[Imagem:Independent 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>. |
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>. |
||
Todo grafo tem ao menos um conjunto independente: o conjunto vazio. Um grafo pode ter vários conjuntos independentes distintos. |
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 |
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=== |
===Definição=== |
||
| Linha 19: | Linha 19: | ||
* <math>\forall V^{\prime\prime} \sub V^\prime : V^{\prime\prime}</math> é um ''conjunto independente'' de <math>G</math> |
* <math>\forall V^{\prime\prime} \sub V^\prime : V^{\prime\prime}</math> é um ''conjunto independente'' de <math>G</math> |
||
==Ver== |
==Ver== |
||
| Linha 25: | Linha 24: | ||
{{esboço}} |
{{esboço}} |
||
[[ |
[[Categoria:Teoria dos grafos]] |
||
[[cs:Nezávislá množina]] |
[[cs:Nezávislá množina]] |
||
Revisão das 18h04min de 23 de setembro de 2008
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
