第一讲布尔函数与判定树 1
§1.1 布尔函数 1
目 录 1
§1.2 图与图性质 6
§1.3 判定树 10
练习题 15
第二讲下界与上界 17
§2.1 隐子与子句 17
§2.2界 18
§2.3弱对称函数 22
练习题 25
§3.1代数判别法 26
第三讲诡函数 26
§3.2弱对称诡函数 29
§3.3 一个反例 33
练习题 37
第四讲图性质 39
§4.1几个例子 39
§4.2 Karp猜想 43
§4.3 团与染色 45
练习题 49
第五讲拓扑方法 51
§5.1单纯复形与欧拉示性数 51
§5.2可塌性 54
§5.3拓扑判别法 57
练习题 61
第六讲不动点的妙用 63
§6.1不动点定理 63
§6.2单纯映象 66
§6.3二分图的性质 70
练习题 71
第七讲置换群的应用 74
§7.1 自同构群的不动点 74
§7.2 Wreath积 76
§7.3单调图性质 79
练习题 80
第八讲六阶图 82
§8.1验证Karp猜想 82
§8.2 对有向图的注记 86
§8.3启迪与思考 88
练习题 89
第九讲随机判定树 90
§9.1 定义 90
§9.2 下界 94
§9.3 Yao-Karp猜想 97
练习题 98
后记 99
参考文献 101