Buenas, se me ocurrió esta solución. Es correcta?
saludos
hola, si es correcta.
a la demo de correctitud le faltaría mostrar que todos los vértices son considerados durante la recorrida. esto es cierto porque es un recorrida bfs (utilizar resultado de k&t). una vez que muestro eso puedo consignar que si no encuentro inconsistencia entonces el conjunto es consistente. de otro modo, no lo podría afirmar para toda instancia.
saludos
a la demo de correctitud le faltaría mostrar que todos los vértices son considerados durante la recorrida. esto es cierto porque es un recorrida bfs (utilizar resultado de k&t). una vez que muestro eso puedo consignar que si no encuentro inconsistencia entonces el conjunto es consistente. de otro modo, no lo podría afirmar para toda instancia.
saludos
Hola, gracias por leerlo y el aporte.
Tendría que aplicarlo en la parte que en que demuestro que si el conjunto de juicios es inconsistente entonces el algoritmo detectará una inconsistencia no?
Porque como recorro todo el grafo, que es inconsistente, y consideré todos los vértices en la recorrida (usaría la propiedad 3.5 y que aplico BFS a todas las componentes conexas), entonces todos fueron etiquetados.
Tendría que aplicarlo en la parte que en que demuestro que si el conjunto de juicios es inconsistente entonces el algoritmo detectará una inconsistencia no?
Porque como recorro todo el grafo, que es inconsistente, y consideré todos los vértices en la recorrida (usaría la propiedad 3.5 y que aplico BFS a todas las componentes conexas), entonces todos fueron etiquetados.
Por lo tanto, necesariamente habrá una arista y un par de nodos que genere una inconsistencia y la detectaré en el paso 20.
saludos
saludos