Emparelhamento Bipartido

Introdução

Dado um grafo bipartido não-direcionado G(E, V), um emparelhamento bipartido é um subconjunto M das arestas de G de tal forma que nenhum par de arestas em M seja incidente a um mesmo vértice. Um emparelhamento bipartido máximo é o emparelhamento bipartido de maior cardinalidade.

Implementações:

Hopcroft-Karp, O(|E|*sqrt(|V|))

Este algoritmo se baseia em encontrar caminhos aumentadores. Um caminho aumentador é um caminho no grafo tal que o primeiro e o último vértices estejam desemparelhados e que as arestas do caminho alternem entre 'emparelhada' e 'não emparelhada'. Dado um caminho aumentador, podemos inverter as arestas desse caminho (i.e. desemparelha quem está emparelhado e emparelha quem está desemparelhado) e obteremos um emparelhamento com uma aresta a mais.

Para otimizar, procura-se vários caminhos aumentadores de menor comprimento ao mesmo tempo. Para isso usamos uma busca em largura (bfs). Após isso fazemos uma busca em profundidade (dfs) sobre esses caminhos para inverter as arestas de cada caminho.

Uma implementação em C++ segue abaixo.

/* --------------------------------------------------------
 * Le o tamanho de cada particao e o numero de arestas k 
 * Cada aresta é dada por 'i j', que indica uma aresta do
 * i-esimo vertice da primeira particao com o j-esimo 
 * vertice da segunda.
 * 
 * Os vertices da primeira particao vão de 0 a n-1 e os da
 * segunda vão de n a n+m-1 (por isso soma '+n' em b).  
 *
 * par[i] representa o vértice que está emparelhado com o
 * vértice i
 * --------------------------------------------------------
 */

#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

#define MAXN 2010
#define MAXM 2010
#define INF 1 << 29

vector < int >adj[MAXN];        /* lista de adjacencias */
int par[MAXN];                  /* (i, par[i]) esta no emparelhamento */
int dist[MAXN];                 /* marca predecessor */ 
int nil;                        /* vertice sentinela */
int n, m;                       /* tamanho de cada particao */
int k;                          /* numero de arestas */
 
bool bfs() {
  queue < int >q;
  dist[nil] = INF;
  for (int v = 0; v < n; v++) {
    if (par[v] == nil) {
      dist[v] = 0;
      q.push(v);
    } else
      dist[v] = INF;
  }
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    if (v != -1)
      for (int j = 0; j < adj[v].size(); j++) {
        int w = par[adj[v][j]];

        if (dist[w] == INF) {
          dist[w] = dist[v] + 1;
          q.push(w);
        }
      }
  }
  return dist[nil] != INF;
}

bool dfs(int v) {
  if (v != nil)
    for (int j = 0; j < adj[v].size(); j++) {
      int u = adj[v][j];
      if (dist[par[u]] == dist[v] + 1 && dfs(par[u])) {
        par[u] = v;
        par[v] = u;
        return true;
      }
    }
  else
    return true;
  dist[v] = INF;
  return false;
}

int bipmatch() {
  nil = n + m;
  for (int v = 0; v < n + m; v++)
    par[v] = nil;
  int matching = 0;
  while (bfs())
    for (int v = 0; v < n; v++)
      matching += (par[v] == nil && dfs(v));
  return matching;
}
int main (){

  int k;

  scanf("%d %d %d", &n, &m, &k);
  for(int i=0; i<k; i++){

    int a, b;
    scanf("%d %d", &a, &b);
    adj[a].push_back(b+n);
    adj[b+n].push_back(a);
  
  }
  int ans = bipmatch();
  printf("%d\n", ans);

  return 0;
}

Benchmarks

[1] Instâncias aleatórias

Referências:

[1] Hopcroft-Karp Algorithm - Wikipedia