Grafos Bipartidos e Emparelhamento

1. O Problema do Casamento Estável

Grafos Bipartidos modelam relacionamentos entre duas classes distintas de entidades: - Candidatos e Vagas de Emprego. - Alunos e Projetos. - Homens e Mulheres (no problema clássico do casamento).

Definição: Um grafo é Bipartido se podemos dividir os vértices em dois conjuntos \(U\) e \(V\) tal que todas as arestas conectam alguém de \(U\) a alguém de \(V\).

2. Emparelhamento Máximo (Maximum Bipartite Matching)

Um Emparelhamento (Matching) é um conjunto de arestas onde nenhum vértice aparece mais de uma vez. Objetivo: Encontrar o maior número possível de pares.

Exemplo: Temos 3 programadores e 3 vagas. - Dev A sabe Java e C++. - Dev B sabe Python. - Dev C sabe Java. - Vaga 1: Java. - Vaga 2: Python. - Vaga 3: C++.

Queremos alocar o maior número de DEVs possível.

3. Redução para Fluxo Máximo

Podemos resolver isso criando um “Super-Source” (\(S\)) e um “Super-Sink” (\(T\)). 1. Crie arestas de \(S\) para todos os nós de \(U\) com capacidade 1. 2. Crie arestas de todos os nós de \(V\) para \(T\) com capacidade 1. 3. Mantenha as arestas originais (\(U \to V\)) com capacidade 1 (ou infinita). 4. O Fluxo Máximo de \(S\) para \(T\) será igual ao tamanho do Emparelhamento Máximo.

4. Algoritmo de Kuhn (Caminhos Aumentantes)

Embora possamos usar Dinic ou Edmonds-Karp, o algoritmo de Kuhn (baseado em DFS) é muito mais simples para codar em competições.

A ideia é: para cada vértice de \(U\), tentamos encontrar um par livre em \(V\). Se o par já estiver ocupado, tentamos gentilmente pedir para que o ocupante atual mude para outro par, liberando a vaga (“Caminho Aumentante”).

Implementação Java

import java.util.*;

public class BipartiteMatching {
    
    int n, m; // n = tamanho de U, m = tamanho de V
    List<List<Integer>> adj;
    int[] pairV; // pairV[v] armazena quem de U está casado com v
    boolean[] visited; // Para evitar ciclos na DFS
    
    public BipartiteMatching(int n, int m) {
        this.n = n;
        this.m = m;
        adj = new ArrayList<>(n);
        for(int i=0; i<n; i++) adj.add(new ArrayList<>());
        pairV = new int[m];
        Arrays.fill(pairV, -1);
        visited = new boolean[n];
    }
    
    public void addEdge(int u, int v) {
        adj.get(u).add(v); // u em [0..n-1], v em [0..m-1]
    }
    
    // Tenta encontrar um par para u
    boolean dfs(int u) {
        visited[u] = true;
        
        for (int v : adj.get(u)) {
            // Se v está livre OU se quem está com v pode mudar
            if (pairV[v] < 0 || (!visited[pairV[v]] && dfs(pairV[v]))) {
                pairV[v] = u; // Match!
                return true;
            }
        }
        return false;
    }
    
    // Retorna o tamanho do matching
    public int maxMatching() {
        int result = 0;
        for (int u = 0; u < n; u++) {
            Arrays.fill(visited, false); // Reseta visitados a cada tentativa
            if (dfs(u)) {
                result++;
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        BipartiteMatching bm = new BipartiteMatching(3, 3);
        // Exemplo: Dev 0 sabe Vaga 0 e 2
        bm.addEdge(0, 0); 
        bm.addEdge(0, 2);
        // Dev 1 sabe Vaga 1
        bm.addEdge(1, 1);
        // Dev 2 sabe Vaga 0
        bm.addEdge(2, 0);
        
        System.out.println("Máximo de Vagas Preenchidas: " + bm.maxMatching());
    }
}

Complexidade

  • No pior caso: \(O(E \times V)\).
  • Na maioria dos casos práticos, é muito mais rápido, comportando-se quase como \(O(E)\).
  • Para grafos muito densos, o algoritmo de Hopcroft-Karp atinge \(O(E \sqrt{V})\), mas é bem mais complexo de implementar.

5. Aplicações (Cobertura Mínima de Vértices)

Teorema de König: Em qualquer grafo bipartido, o número de arestas num emparelhamento máximo é igual ao número de vértices numa cobertura mínima de vértices (Minimum Vertex Cover). Isso resolve problemas como “Onde colocar câmeras de segurança para cobrir todas as ruas de Manhattan?” (Manhattan é uma grid, que é bipartida).

Back to top