[질문] 2-sat 질문

[익명(49.165)]

2-sat의 해를 찾을 때

x와 !x 중에 위상정렬 순서가 뒤인 것을 true로 해주면 되잖아

근데 저렇게 설정하면 왜 SCC의 같은 컴포넌트에 있는 변수들의 값이 같게 되는 거임? 

이거 설명돼있는 자료를 못봤는데 어려워서 증명 안하고 넘어가는 거임?

[익명(59.23)]

false -> true , false -> false 는 다 참인데 true -> false 는 거짓 임으로

[익명(59.23)]

false 부터 책정하는게 더 낫다라고 해야되나?

[ㄱㅆㅇ(49.165)]

그건 알겠는데 그렇게 하면 같은 scc안에 있는 값들이 같다는 걸 어떻게 보장함?

[익명(58.77)]

만들어진 그래프가 skew-symmetric하기 때문에 a랑 b가 같은 scc안에 있으면 ~a랑 ~b도 같은 scc 안에 있음. 같은 scc 안에 속한 a와 b의 참/거짓 여부가 다르다고 가정하면 a와 ~a, 혹은 b와 ~b 중에 하나를 규칙대로 배정하지 않았다는 결론이 나오고, 이건 가정에 모순되니까 증명 끝

[익명(49.165)]

ㄳㄳ