Abrir menu principal

Alterações

Sem alteração do tamanho, 20h07min de 27 de julho de 2009
Checkwiki: limpeza de sintaxe utilizando AWB
[[ImagemFicheiro: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>.
 
===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>
 
===Caracteristicas===
 
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} \setminus{sub V^\prime : V^{\prime\prime}</math> é uma [[coberturaum de''conjunto vertices]]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==
38 303

edições