Hola,
en el práctico pasado probamos la flecha
si el algoritmo retorna false => No existe etiquetado consistente
usando un paso intermedio (hay un ciclo con una cantidad impar de aristas 'diferente'.)
Una demostración un poco más apegada a la sugerencia de la letra seria la siguiente:
BFS etiqueta todos los nodos (con A o B) y por construcción este etiquetado es consistente con los juicios correspondientes a las aristas del árbol generado (de cada componente conexa). Hay que probar que este etiquetado que hace el BFS es el único posible (a menos de invertir todas las etiquetas). Para eso se puede probar que para cualquier camino arbitrario entre dos nodos del árbol, si invertimos la etiqueta del primer nodo del camino, solo se puede mantener la consistencia de con los juicios correspondientes a las aristas del camino si se invierten todas las etiquetas del camino (se puede ver por inducción en la cantidad de nodos del camino). Luego, si el algoritmo devolvió false es porque:
- encontró un juicio (arista) 'igual' entre dos nodos y el BFS los etiquetó de colores diferentes
- encontró un juicio (arista) 'diferentes' y el BFS los etiquetó con el mismo color.
En ambos casos satisfacer el juicio en cuestión implicaría cambiar una sola etiqueta de nodo (de un extremo u otro de la arista),
pero no los dos. Sin embargo, ya se probó que no es posible cambiar una sola etiqueta en un camino (existe un camino entre los nodos inspeccionados porque pertenecen al árbol) y que siga siendo consistente.
eso sería la prueba.
Además les dejo el contraejemplo del algoritmo que mencionaron que coloreaba primero con las aristas diferentes (quitando iguales) y luego chequeaba las iguales.
El algoritmo no funciona por considerar diferentes componentes conexas de las que existen originalmente.
juicios:
1 es diferente a 2
2 es igual a 3
aquí el algoritmo asigna 'A' a 1 y 'B' a 2, luego asigna 'A' a 3 (por se otra componente)
Luego, el algoritmo determina que 2 y 3 son diferentes y por eso retorna false.
Sin embargo existe el etiquetado 1 es A, 2 es B y 3 es B que es consistente.