𝖂𝖎ƙ𝖎𝖊

Conjunto independente

Os nove vértices azuis formam um conjunto independente do grafo acima

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 .[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

é Conjunto independente de

Características

As seguintes indicações são equivalentes:

  • é um conjunto independente de
  • é uma cobertura de vertices de
  • é um conjunto independente de

Ver

Referências

Predefinição:Refbegin

    • Korshunov, A.D. (1974), «Coefficient of Internal Stability», Kibernetika (em Ukrainian), 10 (1): 17–28, doi:10.1007/BF01069014 

Predefinição:Refend

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

talvez você goste