Algoritmos y Estructuras de Datos (VJ1215)

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 V₁ y V₂ de modo que la unión de V₁ y V₂ es V, la intersección de V₁ y V₂ es vacía, y todo arco de E une un vértice de V₁ con un vértice V₂. 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;

}