Conjunto independente

Na teoria dos grafos, um conjunto independente de um grafo ${\displaystyle G}$ é um conjunto ${\displaystyle S}$ de vértices de ${\displaystyle G}$ tal que não existem dois vértices adjacentes contidos em S. Em outras palavras, se ${\displaystyle a}$ e ${\displaystyle b}$ são vértices quaisquer de um conjunto independente, não há aresta entre ${\displaystyle a}$ e ${\displaystyle b}$.^[1]

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

${\displaystyle V^{\prime }}$ é Conjunto independente de ${\displaystyle G\Longleftrightarrow \forall u,v\in V^{\prime }:u\not =v\Rightarrow \left(u,v\right)\notin E}$

Características

As seguintes indicações são equivalentes:

• ${\displaystyle V^{\prime }}$ é um conjunto independente de ${\displaystyle G}$
• ${\displaystyle V\setminus {V^{\prime }}}$ é uma cobertura de vertices de ${\displaystyle G}$
• ${\displaystyle \forall V^{\prime \prime }\subset V^{\prime }:V^{\prime \prime }}$ é um conjunto independente de ${\displaystyle G}$

Ver

• Teoria dos grafos

Referências

Este artigo sobre uma Teoria é um esboço. Você pode ajudar a Wikipédia expandindo-o.