判定树理论导引PDF电子书下载

第一讲布尔函数与判定树 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