Conjunto independente: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Robô: A remover: zh:独立集 (deleted) |
m r2.7.1) (Robô: A adicionar: id:Himpunan bebas |
||
Linha 33: | Linha 33: | ||
[[fr:Stable (théorie des graphes)]] |
[[fr:Stable (théorie des graphes)]] |
||
[[he:קבוצה בלתי תלויה (תורת הגרפים)]] |
[[he:קבוצה בלתי תלויה (תורת הגרפים)]] |
||
[[id:Himpunan bebas]] |
|||
[[ja:独立集合]] |
[[ja:独立集合]] |
||
[[ko:독립집합]] |
[[ko:독립집합]] |
Revisão das 08h30min de 25 de abril de 2012
Este artigo não cita fontes confiáveis. (Agosto de 2010) |
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