Conjunto independente: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m robot Removendo:en |
|||
Linha 1:
O '''Conjunto independente''' de um [[grafo]] é o conjunto dos seus vértices que nunca são adjacentes se agrupados dois a dois (isto é, quando não existe a possibilidade de definir uma aresta a partir de um par de vértices).<br>
Podemos, ainda, definir Conjunto independente máximo, o conjunto independente no qual nenhum vértice pode ser adicionado sem que seja destruída sua independência.
===Definição===
<math>V^\prime</math> é ''Independent Set'' von <math>G \Longleftrightarrow \forall u,v \in V^\prime: u \not= v \Rightarrow \left( u,v \right) \notin E</math>
===Eigenschaften===
Die folgenden Aussagen sind äquivalent:
* <math>V^\prime</math> ist ''Conjunto independente'' de <math>G</math>
* <math>V \setminus{V^\prime}</math> é [[Vertex Cover]] de <math>G</math>
* <math>\forall V^{\prime\prime} \sub V^\prime : V^{\prime\prime}</math> é ''Conjunto independente'' de <math>G</math>
==Ver==
| |||