Pesquisa · Mapa mental
Conjunto independente
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 .
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}
Características
As seguintes indicações são equivalentes:
