Conjunto independente: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Bot: Adicionando: ja:最大独立集合問題 Modificando: en:Independent set problem, ru:Задача о независимом множестве |
|||
| Linha 1: | Linha 1: | ||
[[ |
[[Ficheiro: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>. |
||
| Linha 7: | Linha 7: | ||
===Definição=== |
===Definição=== |
||
<math>V^\prime</math> é ''Conjunto independente'' de <math>G \Longleftrightarrow \forall u,v \in V^\prime: u \not= v \Rightarrow \left( u,v \right) \notin E</math> |
<math>V^\prime</math> é ''Conjunto independente'' de <math>G \Longleftrightarrow \forall u,v \in V^\prime: u \not= v \Rightarrow \left( u,v \right) \notin E</math> |
||
===Caracteristicas=== |
===Caracteristicas=== |
||
As seguintes indicações são equivalentes: |
As seguintes indicações são equivalentes: |
||
* |
*<math>V^\prime</math> é um ''conjunto independente'' de <math>G</math> |
||
*<math>V \setminus{V^\prime}</math> é uma [[cobertura de vertices]] de <math>G</math> |
|||
* |
*<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== |
||
Revisão das 20h07min de 27 de julho 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
