Curso 2024/2025
Un grafo no dirigido G = (V, E) se denomina bipartido si existe una partición del conjunto de vértices V en dos subconjuntos no vacíos V1 y V2 de modo que la unión de V1 y V2 es V, la intersección de V1 y V2 es vacía, y todo arco de E une un vértice de V1 con un vértice V2. Ser bipartido es equivalente a ser 2-coloreable (Recursos opcionales, para saber más: Graph coloring game, Graph coloring).
Por tanto, el problema planteado en el ejercicio 24 equivale a comprobar si un grafo es bipartido (2-coloreable) y, si lo es, averiguar cuáles son los dos subconjuntos del conjunto de vértices.
Este problema se puede resolver empleando tanto la búsqueda en anchura como la búsqueda en profundidad. Mostramos a continuación cómo utilizar ambos tipos de búsqueda para asignar cada vértice a uno de los dos equipos, denotados aquí 1 y 2. Si un vértice pertenece al equipo 1, necesariamente sus vecinos han de pertenecer al equipo 2, y viceversa. Recorremos el grafo en anchura o en profundidad asignando equipos con ese criterio, y si detectamos un conflicto terminamos indicando que no hay solución posible (el grafo no es bipartido).
En las implementaciones que se muestran a continuación nos hemos ahorrado
utilizar un booleano visitado
asociado a cada vértice; en su
lugar, utilizamos el valor -1 de equipo
para indicar que el
vértice no está visitado.
El bucle for (int origen = 0; origen < cantidadDeVertices;
origen++)
se ha puesto porque el grafo no tiene por qué ser conexo:
cuando termina un recorrido en anchura o en profundidad desde un vértice
origen, ese bucle busca el siguiente vértice no visitado para empezar un
nuevo recorrido.
Ambas soluciones tienen coste temporal en el peor caso O(|V| + |E|) gracias a la representación del grafo mediante listas de adyacencia.
vector<int> GrafoNoDirigido::repartirIslas() const { int cantidadDeVertices = vertices.size(); vector<int> equipo(cantidadDeVertices, -1); queue<int> cola; for (int origen = 0; origen < cantidadDeVertices; origen++) if (equipo[origen] == -1) { equipo[origen] = 1; cola.push(origen); while (! cola.empty()) { int v = cola.front(); cola.pop(); for (Arco * arco = vertices[v].primerArco; arco != nullptr; arco = arco->siguiente) if (equipo[arco->vecino] == -1) { equipo[arco->vecino] = 3 - equipo[v]; cola.push(arco->vecino); } else if (equipo[arco->vecino] == equipo[v]) throw string("No existe solucion: el grafo no es bipartido"); } } return equipo; }
void GrafoNoDirigido::repartirIslasDFS(int v, int e, vector<int> & equipo) const { equipo[v] = e; for (Arco * arco = vertices[v].primerArco; arco != nullptr; arco = arco->siguiente) if (equipo[arco->vecino] == -1) repartirIslasDFS(arco->vecino, 3 - equipo[v], equipo); else if (equipo[arco->vecino] == equipo[v]) throw string("No existe solucion: el grafo no es bipartido"); } vector<int> GrafoNoDirigido::repartirIslas() const { int cantidadDeVertices = vertices.size(); vector<int> equipo(cantidadDeVertices, -1); for (int origen = 0; origen < cantidadDeVertices; origen++) if (equipo[origen] == -1) repartirIslasDFS(origen, 1, equipo); return equipo; }