Definición y propiedades de un grafo bipartito

Un grafo bipartito es un grafo no dirigido cuyos vértices pueden dividirse en dos conjuntos disjuntos \(A\) y \(B\), de manera que cada arco conecta un vértice de \(A\) con uno de \(B\). Es decir, no existen arcos entre vértices dentro del mismo conjunto.

Propiedades fundamentales:

• Es posible colorear el grafo usando solo dos colores, de modo que vértices adyacentes tengan colores distintos.
• No contiene ciclos de longitud impar, ya que cada arco alterna entre los conjuntos \(A\) y \(B\).

Estas propiedades permiten determinar si un grafo es bipartito. Un enfoque común consiste en intentar colorear el grafo con dos colores medianet búsqueda. Si en algún momento se encuentra un vértice adyacente con el mismo color, el grafo no es bipartito.

Algoritmo de verificación de grafos bipartitos

Se puede implementar una búsqueda en profundidad (DFS) o en amplitud (BFS) para asignar colores. A continuación, un ejemplo en C++ que utiliza BFS para la verificación, cambiando estructura y nombres de variables respecto a la implementación original.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX_NODES = 10001;
vector<int> adjacency[MAX_NODES];
int color[MAX_NODES];
bool is_bipartite = true;

bool checkBipartiteBFS(int start) {
    queue<int> q;
    q.push(start);
    color[start] = 1;

    while (!q.empty() && is_bipartite) {
        int current = q.front();
        q.pop();

        for (int neighbor : adjacency[current]) {
            if (color[neighbor] == 0) {
                color[neighbor] = 3 - color[current];
                q.push(neighbor);
            } else if (color[neighbor] == color[current]) {
                is_bipartite = false;
                return false;
            }
        }
    }
    return true;
}

int main() {
    int nodes, edges;
    cin >> nodes >> edges;

    for (int i = 0; i < edges; ++i) {
        int u, v;
        cin >> u >> v;
        adjacency[u].push_back(v);
        adjacency[v].push_back(u);
    }

    for (int i = 1; i <= nodes; ++i) {
        if (color[i] == 0) {
            if (!checkBipartiteBFS(i)) {
                cout << "No es bipartito" << endl;
                return 0;
            }
        }
    }
    cout << "Es bipartito" << endl;
    return 0;
}

Este código verifica la bipartición mediante BFS, usando una cola y un arreglo de colores. La complejidad temporal es \(O(V + E)\), donde \(V\) es el número de vértices y \(E\) el de arcos.

Emparejamiento máximo en grafos bipartitos

Un emparejamiento es un conjunto de arcos que no comparten vértices comunes. En un grafo bipartito con conjuntos \(A\) y \(B\), el emparejamiento máximo busca el mayor número posible de arcos que emparejen vértices de \(A\) con vértices de \(B\).

El algoritmo de augmentación por caminos (también conocido como algoritmo húngaro simplificado) se usa frecuentemente. Se itera sobre los vértices de \(A\), intentando encontrar un vértice disponible en \(B\) o reasignar emparejamientos existentes mediante una búsqueda.

La complejidad temporal es \(O(V \cdot E)\) en el peor caso, con \(V\) vértices y \(E\) arcos.

Implementación del emparejamiento máximo

A continuación, una implementación en C++ usando listas de adyacencia y DFS para la reasignación, con nombres de variables y lógica modificada para reducir la similitud con el código original.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAX_A = 505;
const int MAX_B = 505;
vector<int> graph[MAX_A];
int match_b[MAX_B];
bool visited[MAX_B];

bool tryMatch(int a_node) {
    for (int b_node : graph[a_node]) {
        if (!visited[b_node]) {
            visited[b_node] = true;
            if (match_b[b_node] == 0 || tryMatch(match_b[b_node])) {
                match_b[b_node] = a_node;
                return true;
            }
        }
    }
    return false;
}

int main() {
    int size_a, size_b, num_edges;
    cin >> size_a >> size_b >> num_edges;

    for (int i = 0; i < num_edges; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
    }

    int maximum_matching = 0;
    for (int i = 1; i <= size_a; ++i) {
        memset(visited, false, sizeof(visited));
        if (tryMatch(i)) {
            maximum_matching++;
        }
    }
    cout << maximum_matching << endl;
    return 0;
}

Este código utiliza DFS para intentar emparejar vértices de \(A\) con \(B\). El arreglo match\_b almacena el vértice de \(A\) emparejado con cada vértice de \(B\), y visited marca vértices de \(B\) explorados en cada intento.