判定樹理論導引

第一講　布爾函數與判定樹
1.1　布爾函數
1.2　圖與圖性質
1.3　判定樹
練習題
第二講　下界與上界
2.1　隱子與子句
2.2　界
2.3　弱對稱函數
練習題
第三講　詭函數
3.1　代數判別法
3.2　弱對稱詭函數
3.3　一個反例
練習題
第四講　圖性質
4.1　幾個例子
4.2　Karp猜想
4.3　團與染色
練習題
第五講　拓撲方法
5.1　單純復形與歐拉示性數
5.2　可塌性
5.3　拓撲判別法
練習題
第六講 不動點的妙用
6.1　不動點定理
6.2　單純映象
6.3　二分圖的性質
練習題
第七講　置換群的應用
7.1　自同構群的不動點
7.2　Wreath積
7.3　單調圖性質
練習題
第八講　六階圖
8.1　驗證Karp猜想
8.2　對有向圖的注記
8.3　啟迪與思考
練習題
第九講　隨機判定樹
9.1　定義
9.2　下界
9.3　Yar-Karp猜想
練習題
后記
參考文獻