É possível colocar t damas num tabuleiro de xadrez t-por-t de modo que nenhuma delas possa atacar outra? Esta é uma instância do problema dos conjuntos independentes máximos em grafos.
Esta página foi inspirada, em parte, no capítulo 10 do livro de Kleinberg e Tardos.
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 |
Um conjunto independente (= independent set) em um grafo é um conjunto de vértices dois a dois não adjacentes. Portanto, um conjunto S de vértices é independente se nenhuma aresta tem ambas as pontas em S. Conjuntos independentes também são conhecidos como conjuntos estáveis.
Um conjunto independente em um grafo G é máximo se não existe outro maior em G. Em outras palavras, um conjunto independente X em G é máximo se não existe um conjunto independente S em G tal que ⎮S⎮ > ⎮X⎮.
Problema do Conjunto Independente Máximo: Encontrar um conjunto independente máximo em um grafo.
O problema é notoriamente difícil.
É claro que um algoritmo de força bruta
,
que examina todos os 2n subconjuntos
do conjunto de vértices do grafo,
resolve o problema.
Mas não se descobriu (ainda?)
um algoritmo que seja substancialmente mais rápido.
É possível até que um tal algoritmo não existe.
(Veja a página Complexidade e problemas NP-completos.)
A variante de decisão
do problema pede apenas uma resposta booleana:
dado um grafo G e um número natural k,
decidir se G tem um conjunto independente
com k ou mais vértices.
Mas essa variante não é mais fácil que o problema original.
Exemplo A. A figura mostra conjuntos independentes máximos em dois grafos (vértices vermelhos no primeiro grafo e vértices azuis no segundo).
9por seu expoente favorito.)
Embora o problema de conjunto independente máximo seja muito difícil em geral, sua restrição a alguns tipos de grafos é fácil. Considere os dois casos a seguir.
Grafos de intervalos. Uma coleção de intervalos na reta pode ser representada por um grafo. Cada intervalo é um vértice e dois vértices são adjacentes se os correspondentes intervalos não são disjuntos, ou seja, se têm um ou mais pontos em comum. Assim, uma coleção de intervalos é disjunta se e somente se o correspondente conjunto de vértices é independente. Portanto, o problema da coleção disjunta máxima de intervalos é um caso especial (ou seja, uma coleção de instâncias) do problema de conjunto independente máximo. De acordo com a página Intervalos disjuntos, existe um algoritmo linearítmico para esse caso especial.
Florestas. O problema do conjunto independente máximo é fácil quando restrito a florestas. A descrição de um algoritmo eficiente para esse caso usa o seguinte conceito: uma folha de uma floresta é um vértice que tem exatamente 1 vizinho. Toda floresta com pelo menos uma aresta tem pelo menos uma folha.
O algoritmo que calcula um conjunto independente máximo numa floresta F pode ser descrito assim. Cada iteração começa com uma floresta L. (No começo da primeira iteração, L é F.) Enquanto L tiver pelo menos uma aresta,
| escolha uma folha v da floresta L, |
| seja w o único vizinho de v em L, |
| remova as arestas de L que incidem em w, |
| remova o vértice w de L. |
No início da última iteração, L não tem arestas. Nesse momento, o conjunto de vértices de L é um conjunto independente máximo em F.
Pode-se dizer que esse algoritmo é guloso. A correção do algoritmo decorre do seguinte invariante: no começo de cada iteração, o conjunto de vértices de L inclui algum conjunto independente máximo de F. Esse invariante segue do seguinte
Teorema: Em qualquer floresta, toda folha pertence a algum conjunto independente máximo.
Prova: Seja F a floresta em questão, seja v uma folha de F, e seja w o único vizinho de v. Seja X um conjunto independente máximo de F. Um de v e w pertence a X, pois caso contrário X ∪ { v } seria um conjunto independente, o que contraria a maximalidade de X. Agora considere as seguintes alternativas. Se v ∈ X então X tem a propriedade desejada. Se w ∈ X então o conjunto (X − { w }) ∪ { v } é um conjunto independente máximo e contém v, CQD.
A implementação eficiente do algoritmo exige algum esforço: é preciso inventar uma representação da floresta L que seja mais apropriada que uma simples matriz de adjacência.
Toda floresta tem pelo menos uma folha.
Em qualquer árvore, o conjunto de todas as folhas é um conjunto independente máximo.
Em qualquer árvore, o conjunto de todas as folhas é um conjunto independente maximal.
Se X é um conjunto indendente máximo de uma árvore com 3 ou mais vértices, então X não contém vizinhos de folhas.
Um conjunto independente I em um grafo G é maximal se não for subconjunto próprio de algum outro conjunto independente, ou seja, se não existe um conjunto independente J tal que J ⊃ I.
É claro que todo conjunto independente máximo é maximal, mas a recíproca está muito longe de ser verdadeira. (Veja um dos exercícios abaixo.)
Exemplo C. A figura mostra um conjunto independente maximal (vértices vermelhos) no grafo do cubo.
É fácil calcular um conjunto independente maximal. O seguinte algoritmo recebe um grafo G e devolve o vetor característico de um conjunto independente maximal:
| Independente-Maximal (G) |
| 1 . para cada vértice v |
| 2 .ooo x[v] := 0 |
| 3 . para cada vértice v |
| 4 .ooo x[v] := 1 |
| 5 .ooo para cada vizinho w de v |
| 6 .oooooo se x[w] = 1 |
| 7 .ooooooooo x[v] := 0 |
| 8 . devolva x |
Ao longo da execução do algoritmo, seja X o conjunto de todos os vértices v tais que x[v] = 1. No começo de cada execução da linha 4, valem as seguintes propriedades invariantes:
Portanto, no início da linha 8, o conjunto independente X é maximal.
Consumo de tempo. Quanto tempo o algoritmo Independente-Maximal consome para processar um grafo com n vértices? Considere inicialmente o bloco de linhas 3-7. O consumo de tempo desse bloco é proporcional ao número de execuções de linha 6. Para cada valor fixo de v, a linha 6 é executada para cada vizinho de v. Como cada vértice tem menos que n vizinhos, o número total de execuções da linha não passa de n×(n − 1). Portanto, o bloco de linhas 3-7 consome Ο(n²) unidades de tempo.
Como o par de linhas 1-2 consome Θ(n) unidades de tempo, o consumo total do algoritmo é de Ο(n²) unidades de tempo.
Se adotarmos n² como tamanho do grafo, podemos dizer que o algoritmo é linear.
Para fazer um cálculo mais preciso, podemos levar em conta o número de arestas, m, do grafo e adotar n + m como tamanho do grafo. Nesse caso, o cálculo do número de execuções da linha 6 precisa ser refeito. Ao examinar um vizinho de v na linha 5, o algoritmo está examinando uma aresta do grafo. Nesse processo, cada aresta pq do grafo é examinada no máximo duas vezes (primeiro com pq = vw e depois com pq = wv). Se o grafo for representado por listas de adjacência, a linha 6 será executada no máximo 2m vezes. (Essa estimativa é muito menor que n² se m for muito menor que n².) Assim, o consumo total do algoritmo é de
Ο(n + m)
unidades de tempo.