MIUP 2013 - Um problema de Grafos

Não tive oportunidade de escrever no blog nas últimas semanas. Para compensar, hoje vou falar de um problema um pouco mais difícil do o habitual: o problema B da MIUP 2013 - Say Geese.

Objectivo do problema:

Dado um grafo não-dirigido com N (<= 11) vértices e E (<= 45) arestas (edges), quantos subconjuntos de arestas formam um grafo conexo?

Um pouco sobre Grafos:

Um grafo pode ser visto como a representação de um conjunto de objectos (vértices) e as ligações (arestas) entre esses objectos. Uma rede social pode ser vista como um grafo onde os vértices representam as pessoas e as arestas entre 2 pessoas representam uma relação de amizade entre as mesmas.

Um grafo conexo é um grafo onde todos os vértices estão ligados entre si percorrendo uma ou mais arestas. Assim, na imagem abaixo, o grafo da esquerda não é conexo porque não existe nenhuma ligação entre o João e as outras pessoas. Por outro lado, o grafo da direita é conexo pois todos estão ligados (ainda que indirectamente).

Abordagem base:

Voltando ao problema, quando escolhemos um edge que liga os vértices A e B, unimos não só A a B, mas também todos os vértices que tinham sido já unidos a A ou a B.

Podemos imaginar que estamos a agrupar os vértices. Quando ligo A a B, o grupo do A fica unido ao grupo do B e passam a formar um só grupo. Assim, um subconjunto de arestas forma um grafo conexo se todos os N vértices estiverem no mesmo grupo (ver imagem acima, da esquerda para a direita).

Para simular este processo, podemos ter um array que nos diz qual é o grupo de cada vértice. Inicialmente, todos os vértices estão dispersos, podemos dizer que não têm grupo. Usando o exemplo 2 do enunciado, temos 4 vértices. inicialmente os grupos são {0,0,0,0}, onde 0 = sem grupo.

Se escolhermos o edge que liga 0 a 1, então passam a formar um grupo - {1,1,0,0}. índices 0 e 1 estão no grupo 1, índices 2 e 3 sem grupo. Depois, 

• Se escolher o edge 1 - 2, o 2 (que não tem grupo) passa a integrar o grupo do 1: {1,1,1,0}
• Se em vez de 1 - 2, escolher o 2 - 3, então o 2 e o 3 estão num grupo diferente: {1,1,2,2}. Se escolhêssemos o edge 0 - 3 a seguir, então ficavam todos no mesmo grupo {1,1,1,1}.

Em pseudo-código, este algoritmo seria algo do género:

Contar(edge_actual, grupos) {

    Se os vértices já formam um grafo conexo

         resultado = 1

    Senão

         resultado = 0
    // ignora este edge e passa ao próximo
    resultado += Contar(edge_actual+1, grupos)
    // une os grupos dos vértices ligados pelo edge actual
    novos_grupos = Une(grupos, edge_actual) 
    resultado += Contar(edge_actual+1, novos_grupos)
    return resultado
}

Aplicar programação dinâmica

Existem 2⁴⁵ subconjuntos de arestas e 2⁴⁵ > 10¹², por isso é inviável testar todos os subconjuntos.

Na abordagem base, o estado da pesquisa pode ser determinado pelo grupo de cada vértice e o edge actual a processar.

À medida que seleccionamos vários edges, vamos estar a repetir o mesmo estado muitas vezes - condição natural para o uso de programação dinâmica. Notem também que muitos estados são simétricos, isto é {1,1,2,2} é simétrico de {2,2,1,1} porque o número do grupo é irrelevante, só queremos saber que vértices já estão ligados entre si.

Com um pouco de experimentação, podemos ver que no máximo existem cerca de 4 milhões de estados diferentes, o que parece um número razoável. 

O problema é que o estado é relativamente complexo. Reparem que como só existem no máximo 11 vértices, nós só podemos ter no máximo 5 grupos desconexos (5 pares de vértices) um 6º edge liga obrigatoriamente o vértice sem grupo a um vértice que tem grupo ou 2 vértices com grupo. 
Deste modo, o grupo de cada vértice é um número entre 0 e 5.

Uma hipótese para guardar os valores calculados para cada estado, é a utilização de uma Trie. Cada nó da Trie representa o valor do grupo de cada vértice. Exemplo: 1 -> 1 -> 2 -> 2.

Conclusão: 

Existem várias formas de abordar este problema, esta é apenas uma delas. Sugiro também a consulta da sessão de discussão de problemas, onde é apresentada uma abordagem um pouco mais teórica, explorando mais as propriedades dos grafos.

A minha implementação (em estilo concurso de programação, não de desenvolvimento de software):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89

#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int MAXV = 11; const int MAXE = 45; const int BASE = 6; int N, E, ex[MAXE], ey[MAXE]; struct Node { long long val; Node* next[BASE]; Node() { memset(next, 0, sizeof next); } } root[MAXE+1]; long long Go(int e, int* vc) { Node* cur = &root[e]; int i, components[MAXV], recolor[MAXV]={}, maxc=0, a=ex[e], b=ey[e], oldc, newc, max_comp=0; bool found = true; for (i = 0; i < N ; i++) { // procura este estado na trie if (!cur->next[vc[i]]) { // mesmo que não encontre, cria os nós correspondentes na trie found = false; // porque depois do cálculo, temos de adicionar à trie cur->next[vc[i]] = new Node(); } cur = cur->next[vc[i]]; components[i] = vc[i]; if (components[i] > max_comp) max_comp = components[i]; } if (found) // encontrei por isso o valor já foi calculado return cur->val; if (e == E) // chegamos ao fim dos edges return cur->val = 0; // uma hipotese é simplesmente ignorar este edge e passar ao próximo long long res = Go(e+1, components); // merge das componentes if (components[a] != components[b] || components[a] == 0) { if (components[a] == 0) { if (components[b] == 0) components[b] = ++max_comp; components[a] = components[b]; } else { if (components[b] == 0) components[b] = components[a]; else { oldc = max(components[a], components[b]); newc = min(components[a], components[b]); for (i = 0; i < N ; i++) if (components[i] == oldc) components[i] = newc; } } } // recoloring das componentes para evitar estados simétricos for (i = 0; i < N; i++) { if (components[i]) { if (!recolor[components[i]]) recolor[components[i]] = ++maxc; components[i] = recolor[components[i]]; } } res += Go(e+1, components); return cur->val = res; } void TrieInsert(int e, long long val) { Node* cur = &root[e]; for (int i = 0; i < N; i++) { if (!cur->next[1]) cur->next[1] = new Node(); cur = cur->next[1]; } cur->val = val; } int main() { int i, comps[MAXV] = {}; scanf("%d %d", &N, &E); for (i = 0; i < E; i++) { scanf("%d %d", &ex[i], &ey[i]); // existem 2^(E-i) subconjuntos de eges usando os edges i,i+1,..,E-1 TrieInsert(i, 1LL << (E-i)); } TrieInsert(E, 1); printf("%lld\n", Go(0, comps)); return 0; }