Conjunto independente
Aspeto mover para a barra lateral ocultar
Os nove vértices azuis formam um conjunto independente do grafo acima
Na teoria dos grafos, um conjunto independente de um grafo G {\displaystyle G} é um conjunto S {\displaystyle S} de vértices de G {\displaystyle G} tal que não existem dois vértices adjacentes contidos em S. Em outras palavras, se a {\displaystyle a} e b {\displaystyle b} são vértices quaisquer de um conjunto independente, não há aresta entre a {\displaystyle a} e b {\displaystyle b} .
é um conjunto
S
{\displaystyle S}
de vértices de
G
{\displaystyle G}
e
b
{\displaystyle b}
são vértices quaisquer de um conjunto independente, não há aresta entre
a
{\displaystyle a}
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
V ′ {\displaystyle V^{\prime }} é Conjunto independente de G ⟺ ∀ u , v ∈ V ′ : u ≠ v ⇒ ( u , v ) ∉ E {\displaystyle G\Longleftrightarrow \forall u,v\in V^{\prime }:u\not =v\Rightarrow \left(u,v\right)\notin E}
é Conjunto independente de
G
⟺
∀
u
,
v
∈
V
′
:
u
≠
v
⇒
(
u
,
v
)
∉
E
{\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:
- V ′ {\displaystyle V^{\prime }} é um conjunto independente de G {\displaystyle G}
- V ∖ V ′ {\displaystyle V\setminus {V^{\prime }}} é uma cobertura de vertices de G {\displaystyle G}
- ∀ V ′ ′ ⊂ V ′ : V ′ ′ {\displaystyle \forall V^{\prime \prime }\subset V^{\prime }:V^{\prime \prime }} é um conjunto independente de G {\displaystyle G}
é uma 
é um conjunto independente de
G
{\displaystyle G}
Ver
Referências
- Korshunov, A.D. (1974), «Coefficient of Internal Stability», Kibernetika (em Ukrainian), 10 (1): 17–28, doi:10.1007/BF01069014 !CS1 manut: Língua não reconhecida (link)