Graph

infwinston

附件的上課note參考自建中講義及各blog
(建中講義有諸多例題，有空一定要練習看看 http://pisces.ck.tp.edu.tw/~peng ... 9c44f1b62521f8358c5)
2SAT 證明
http://pisces.ck.tp.edu.tw/~peng ... 70e78ce15ea7c5a6faa


關於今天的圓桌武士問題，後來想到證明了，
不想被雷的就別看吧XD

現在欲證明的就是，若點雙連通分量中含有奇圈，則所有在點雙連通分量中的點都會被奇圈cover
利用數學歸納法證明：
base case 三點顯然成立，假設 n 個點成立，此時考慮加進來一個新點 v ，
v 至少會和 n 個點其中兩個點直接相連（否則新圖就不是點雙連通了），記做 A 點和 B 點，

又已知A一定會被一個奇圈所cover（歸納法假設）
又B總是會有一條路徑通到該奇圈上，且必定存在一條路徑使得第一個碰到的點不為A，記做C （這邊證起來有點小繁瑣= = 先感性認為是對的）
這時候，VA-弧X-弧Z-BV 形成一個圈，VA-弧Y-弧Z-BV形成一個圈，又已知 弧X 弧Y 兩者奇偶性必定相反(因為弧X+弧Y是奇數)
因此這兩圈當中必定有一個是奇圈，於是 n+1 case 成立，
由數學歸納法得證：若點雙連通分量中含有奇圈，所有在點雙連通分量中的點都會被奇圈cover

至於證完這件事後，事實上理解掉這題還有一些步驟，就留給大家思考吧!