Buenas, quería saber si esta solución está bien, y en caso afirmativo si está bien justificado.
Mi pseudocodigo es el siguiente:
1. Crear un grafo G1 donde cada nodo representa una mariposa y hay una arista (x,y) si el par {x,y} fue etiquetado como iguales
2. Obtener las componentes conexas de G1 con BFS
3. Para cada par etiquetado como distintas, si el par pertenece a la misma componente conexa, el etiquetado es inconsistente.
4. Si en (3) no se detectan inconsistencias, construir un grafo G2 donde cada nodo representa una componente conexa y hay una arista entre dos nodos (x,y) si alguna de las mariposas de la componente representada por x esta etiquetada como distinta a alguna de las mariposas de la componente representada por y.
5. Chequear si el grafo G2 es bipartito usando BFS. Si lo es, el etiquetado es consistente. Si no lo es, es inconsistente.
Justificación de la corrección:
a. Hay un par (x,y) en la misma componente conexa del grafo G1 que fue etiquetado como distinto. Como x e y son parte de la misma componente conexa, hay un camino en G1 de x a y. Pero estas aristas representan ejemplares etiquetados como iguales, y como "ser iguales" es una relación de equivalencia, es transitiva, por lo que x e y son iguales. Pero por hipótesis fueron etiquetadas como distintas, por lo que el etiquetado es inconsistente.
b. El grafo G2 no es bipartito. Ya establecimos en (a) que todos los nodos de la misma componente conexa de G1 representan mariposas de la misma especie, por lo que podemos asignar las componentes (y por lo tanto los nodos de G2) a especies. Entonces una arista de G2 entre las componentes ci y cj implica que esas componentes corresponden a especies distintas, ya que hay al menos una etiqueta de distintas entre una mariposa de ci y una de cj.
Como el grafo no es bipartito, por 3.15 del libro hay un ciclo de largo impar. Sea (c1, c2, ..., cn, c1) dicho ciclo. Sin perder generalidad, digo que c1 es de especie A, entonces c2 es de especie B, y en general, los nodos de indice impar quedarán etiquetados como especie A y los de indice par como especie B. Como el ciclo es de largo impar, cn es de especie A, pero hay una arista de cn a c1, con lo que c1 es de especie B, y así llegamos a una inconsistencia en los etiquetados.
Queda demostrado que si el algoritmo detecta una inconsistencia es porque los etiquetados son inconsistentes. Quiero ver que si el algoritmo no encuentra inconsistencias, entonces el etiquetado es consistente.
Si el algoritmo no encuentra inconsistencias, entonces por lo visto anteriormente puedo asignar a cada componente una especie, y como no hay etiquetas de distintas entre los pares de mariposas que están en la misma componente, cada componente tendrá una única etiqueta. Entonces para todo par etiquetado como iguales se cumple que efectivamente las mariposas fueron asignadas a la misma especie.
Como el grafo G2 es bipartito, cada par de componentes ci, cj tales que hay al menos una etiqueta de distintas entre una mariposa de ci y una de cj puede ser etiquetado como especies distintas. Entonces para todo par etiquetado como diferentes se cumple que las mariposas fueron asignadas a especies distintas.
Gracias!