Fundamentos de Grafos Bipartitos

Concepto y Definición

Un grafo bipartito es una estructura especial en teoría de grafos donde el conjunto de vértices V puede dividirse en dos subconjuntos disjuntos, digamos P y Q, de modo que toda arista conecte un vértice de P con uno de Q. Esto implica que no existen aristas entre vértices pertenecientes al mismo subconjunto.

En términos sencillos, se trata de un grafo cuyos nodos se agrupan en dos clases, y las conexiones únicamente ocurren entre nodos de clases distintas.

Propiedades Fundamentales

Las condiciones necesarias y suficientes para que un grafo sea bipartito son:

1. El grafo debe tener al menos dos vértices.
2. Todos los ciclos presentes en el grafo deben tener longitud par.

La segunda propiedad se entiende así: si recorremos un ciclo comenzando desde un vértice del conjunto P, después de un número impar de aristas estaremos en Q, y después de un número par estaremos de vuelta en P. Como el ciclo cierra en el vértice inicial (que pertenece a P), la cantidad total de aristas recorridas debe ser par.

Detección de Grafos Bipatritos

Existen dos enfoques principales para verificar si un grafo es bipartito:

• Coloración bipolar: Se asigna uno de dos colores a cada vértice de forma alternada. Partiendo de un nodo arbitrario, se colorea con el color A; sus vecinos reciben el color B; los vecinos de estos reciben el color A, y así sucesivamente. Si en algún momento se intenta colorear un nodo ya pintado con un color distinto al que le corresponde, el grafo no es bipartito.
• Búsqueda de ciclos impares: Mediante BFS o DFS se recorre el grafo buscando ciclos de longitud impar. Si se encuentra alguno, el grafo no es bipartito; en caso contrario, sí lo es.

Emparejamientos en Grafos Bipartitos

Definiciones Clave

Un emparejamiento en un grafo bipartito es un conjunto de aristas que no comparten vértices entre sí. Es decir, ningún par de aristas del emparejamiento incide sobre el mismo nodo.

Conceptos derivados:

• Emparejamiento perfecto: aquel donde todos los vértices están cubiertos por alguna arista del emparejamiento.
• Emparejamiento maximal: aquel al que no se puede añadir ninguna arista adicional sin violar la restricción de no compartir vértices.
• Emparejamiento máximo: el emparejamiento maximal con mayor cantidad de aristas entre todos los posibles.

Todo emparejamiento perfecto es también máximo, pero no necesariamente al revés.

Algoritmo Húngaro para Emparejamiento Máximo

Caminos de Aumento

Sea M un emparejamiento del grafo. Un camino alternante es aquel cuyas aristas alternan entre pertenecer y no pertenecer a M. Si además las aristas inicial y final del camino no están en M, se denomina camino de aumento.

La propiedad clave es que en un camino de aumento, las aristas fuera de M superan por una a las que están dentro de M. Por tanto, invirtiendo la pertenencia de las aritas del camino (las que estaban en M salen, y las que no estaban entran), el emparejamiento crece en una arista.

Procedimiento del Algoritmo

El algoritmo Húngaro funciona intentando emparejar cada nodo del primer conjunto. Para cada nodo:

1. Se examinan todas sus aristas hacia el segundo conjunto.
2. Si el nodo destino está libre, se establece el emparejamiento.
3. Si está ocupado, se solicita al nodo que lo tiene emparejado que busque una alternativa. Si la encuentra, libera la posición; si no, se prueba la siguiente arista.

Cuando ya no quedan caminos de aumento por encontrar, el emparejamiento actual es máximo.

Implementación en C++

Problema de referencia: P3386 - Plantilla de emparejamiento máximo en grafo bipartito.

#include <bits/stdc++.h>
using namespace std;

const int LIM = 505;

int totalLeft, totalRight, edgeCount;
int adjMatrix[LIM][LIM];
int partner[LIM];
bool visited[LIM];
int matchCount = 0;

bool tryAugment(int node) {
    for (int candidate = 1; candidate <= totalRight; candidate++) {
        if (adjMatrix[node][candidate] && !visited[candidate]) {
            visited[candidate] = true;
            if (partner[candidate] == 0 || tryAugment(partner[candidate])) {
                partner[candidate] = node;
                return true;
            }
        }
    }
    return false;
}

int main() {
    scanf("%d%d%d", &totalLeft, &totalRight, &edgeCount);
    for (int i = 0; i < edgeCount; i++) {
        int from, to;
        scanf("%d%d", &from, &to);
        adjMatrix[from][to] = 1;
    }
    for (int i = 1; i <= totalLeft; i++) {
        memset(visited, false, sizeof(visited));
        if (tryAugment(i)) {
            matchCount++;
        }
    }
    printf("%d\n", matchCount);
    return 0;
}

Resolución mediante Flujo Máximo

Otra forma de abordar el emparejamiento máximo es modelándolo como un problema de flujo máximo. Para ello:

1. Se crea un nodo fuente que conecta con todos los vértices del primer conjunto.
2. Se crea un nodo sumidero al que se conectan todos los vértices del segundo conjunto.
3. Todas las aristas, incluidas las de fuente y sumidero, tienen capacidad 1.

El valor del flujo máximo coincide con el tamaño del emparejamiento máximo, ya que cada unidad de flujo representa una arista seleccionada, y la restricción de capacidad 1 garantiza que ningún nodo participe en más de un emparejamiento.

Implementación con Dinic

#include <bits/stdc++.h>
using namespace std;

typedef long long int64;

const int MAXN = 550;
const int MAXEDGES = 10050;
const int INF = 0x3fffffff;

int leftCount, rightCount, edgeTotal, source, sink;

struct Edge {
    int dest, capacity, flow, nextEdge;
};

Edge edges[MAXEDGES];
int head[MAXN], edgePtr = 1;
int dist[MAXN], current[MAXN];

void addEdge(int u, int v, int cap) {
    edges[++edgePtr] = {v, cap, 0, head[u]};
    head[u] = edgePtr;
    edges[++edgePtr] = {u, 0, 0, head[v]};
    head[v] = edgePtr;
}

bool buildLevelGraph() {
    for (int i = 0; i <= leftCount + rightCount + 2; i++) {
        dist[i] = INF;
        current[i] = head[i];
    }
    queue<int> bfsQueue;
    dist[source] = 0;
    bfsQueue.push(source);
    while (!bfsQueue.empty()) {
        int front = bfsQueue.front();
        bfsQueue.pop();
        for (int e = head[front]; e; e = edges[e].nextEdge) {
            if (edges[e].capacity - edges[e].flow > 0 && dist[edges[e].dest] == INF) {
                dist[edges[e].dest] = dist[front] + 1;
                bfsQueue.push(edges[e].dest);
            }
        }
    }
    return dist[sink] != INF;
}

int64 totalFlow = 0;

int sendFlow(int node, int bottleneck) {
    if (node == sink) {
        totalFlow += bottleneck;
        return bottleneck;
    }
    int pushed = 0;
    for (int &e = current[node]; e; e = edges[e].nextEdge) {
        int residual = edges[e].capacity - edges[e].flow;
        if (dist[edges[e].dest] == dist[node] + 1 && residual > 0) {
            int sent = sendFlow(edges[e].dest, min(bottleneck - pushed, residual));
            if (sent > 0) {
                edges[e].flow += sent;
                edges[e ^ 1].flow -= sent;
                pushed += sent;
                if (pushed == bottleneck) break;
            }
        }
    }
    return pushed;
}

void computeMaxFlow() {
    while (buildLevelGraph()) {
        sendFlow(source, INF);
    }
    printf("%lld\n", totalFlow);
}

int main() {
    scanf("%d%d%d", &leftCount, &rightCount, &edgeTotal);
    for (int i = 0; i < edgeTotal; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(u, v + leftCount, 1);
    }
    source = leftCount + rightCount + 1;
    sink = leftCount + rightCount + 2;
    for (int i = 1; i <= leftCount; i++) {
        addEdge(source, i, 1);
    }
    for (int i = 1; i <= rightCount; i++) {
        addEdge(i + leftCount, sink, 1);
    }
    computeMaxFlow();
    return 0;
}

Cobertura Mínima de Vértices

Definición

Una cobertura de vértices es un subconjunto de nodos tal que toda arista del grafo tiene al menos uno de sus extremos en dicho subconjunto. La cobertura mínima es aquella con la menor cantidad de vértices posible.

Relación con el Emparejamiento Máximo

En un grafo bipartito, el tamaño de la cobertura mínima de vértices es igual al tamaño del emparejamiento máximo (Teorema de König). El procedimiento para obtenerla es:

1. Ejecutar el algoritmo de emparejamiento máximo.
2. Partiendo desde los nodos del conjunto derecho que no fueron emparejados, recorrer caminos alternantes.
3. Marcar todos los vértices visitados durrante este recorrido.
4. La cobertura mínima se compone por los nodos del lado derecho que no fueron marcados, más los nodos del lado izquierdo que sí lo fueron.