录 第一章预备知识 §11集合 §1序 §13图 §14群 1曲面 ,18 I6注记 曾,4 第二章图中的树 26 §21树与上树∴ §22确向树与确向上树 2.3注记, 第三章图中的空间 630二分空间 31循环,上循环和双循环 43 §32循环空间 46 §33上循环空间 53 34双循环空间 §35注记 第四章可平面图
目录 §41 Euler公式的利用 §42 Jordan曲线定理 76 §43唯一性 §44凸表示 §4.5注记 .91 第五章平面性 51浸入 52吴(文俊)- Iuttte定理 .98 3平面性辅助图 06 54主要定理 ··,·甲 ,112 55注记 118 第六章高斯交叉问题 ,121 6.1交叉序列 121 62Dehn定理 126 弱6.3高斯猜想 132 §64注记 140 第七章乎面嵌入 142 71左和右确定 鲁··,,、着着B ,,142 g72禁用构形 148 g7.3基本序表征.,,157 §74平面嵌入的数目 ...167 §75注记 175 第八章纵横可嵌入性 ,176 §81纵樻嵌入 176
目录 52叁可嵌入性 185 §3双可联入性 §84单可嵌入性 203 §85注记 第九章网格可嵌入性 213 §9许可性 ..213 92隅序列 220 s3一般判准 227 94特殊判准 ∴.235 §95注记 243 第十章多面形的同构 245 3101多面形的自同构 245 §102 Euler和非uler码 252 810.3多面形的同构 262 §104注记 269 第十一章图的分解 271 111双连通分解 Pasana §11.2叁连通分解……276 113平面分解 6114页分解 ,,288 §11.5纵横分解 294 §116注记 ,,298 第十二章曲面可嵌入性 300 §121必要条件 300
目录 122上可嵌入性 ,305 s123商嵌入 311 §124下可嵌入性 ,,320 125注记 ,,,329 第十三章极值问题 131最优凸嵌入 ,332 s132最短三角剖分 338 §133极少折数嵌入 ,344 §134极小面积嵌入 §135注记 359 第十四章图和上图拟阵 5141二分拟阵 361 142正则性 §143图性与上图性 ,P甲 §144注记 384 第十五章纽结不变量 .386 §151纽结类型 386 §152图的模型 391 8153纽结多项式 ,,,398 §154注记 ,,411 参考文献 ,,413 名词索引(汉英) ,,, ,462 名词索引(英汉) 479
第一章 预备知识 为方便,全书采用通常的逻辑约定:和,积,否定,蕴意, 等价,任意量和存在量分别用符号:∨,∧,",→,兮,V和彐 在正文中,(i表示在第i章的第节中的第k项 在文献中,{表示参考文献中的第k项.其中k由该项 作者(们)姓的前几个字母接着为数字所组成姓氏按字母序 排.同样的作者(们则用数字区别不同的文章或其它出版物 §1.1集合 个集合就是具有共性的一类对象的全体,这个对象可 以是数、符号、字母,甚至还可以为集合,当然,这个集合不 包括所定义的那个集合本身以免自相矛盾,其中的对象称为这 个集合的元素.我们总是用小写斜体表示元素而大写的字母为 集合·说法“x是(不是)集合M的一个元素用如下的符号表 小 ∈M(xM) 个集合通常用一种姓质所刻划,例如
第一章预备知识 M={x|x≤4,正整数 一个集合M的基数(当M为有限时即它的元素的数目)用 M|表示.对于上面定义的M,自然,|M|=4. 令A,B是二个集合.如果(a)(a∈A→a∈B),则称A 为B的子集.记为A≌B.进而,定义三个主要的运算:并、 交和差分别如下所示 AUB={ax|(x∈A)(x∈B)} 1.1.1) A∩B={x(x∈A)∧(x∈B)}; (112) \B={c|{x∈A)∧(xgB)} (113) 奶果BSA,则A\B=A-B用B(A)表示,并称之为B对 A的补.如果所有的集合都是g的子集,则集合A对9的补 简单地写为A.空集就是一个没有任何元素的集合,总是用 表示,对于9的子集间的上述运算服从如下的规律 S1排中律:Acg A∩A=AUA A (114 S2交换律:VA,B≤9, AUB=BUA (1.15) A∩B=B∩A
511集合 s3结合律:vA,B,Cg, A∪(B∪C)=(AUB)∪C A∩(BnC)=(4^B)∩C s4吸收律:ⅤA,B An(AUB)=AU(A∩B s5分配律:VA,B,C∈!, A∪(B∩C)=(AUB)n(AUC); (118) A∩(BUC)=(A∩B)∪(A∩C) S6通界律:VA∈9, 0∩A=6,UA=A; (1.19) g∩A=A,gUA=9 s7单补律:Acg, A∩A=四; AU A (1.110) 由这些定律出发,可以得到很多重要结果.这里仅列出一 些将会用的 定理1.11VAg且
第一章预备知识 (Xsg)((A∩X=A)V(A∪X=X) A=; (L.111) X≤g2)[(A∩X=X)v(AUX=A) A=5 定理1.12VA,Bc9, A∩B=A分A∪B=B (1.112) 定理113VA,B,Ccg, (A∩B=A∩C)A(AUB=AUC) E C 1.13) 定理1.14VA∈Ω, A= A (1L14) 定理115VA,B∈9 AuB=A∩B: (1.115) A∩B=A∪B 由上所述,可以看出D=9和5=國.进而,还可以看出 对称性(或者说对偶性}任何一个关于,∩,,的结论均可通 过交换∪和∩,和g而得出另一个结论 对于A,BC9,从A到B的-…个单射是指这样的一个映 象α:A→B使得:a,b∈A, a≠b→a(a)≠a(b
§12序 单射也称为1-1对应.一个满射则是这样的一个映象A A→B使得:∈B, 3a∈A,B(a)=b 如果一个映象既是单射又是满射,则称为双射.如果两个集合 之间有一个双射,则称它们是同构的.用A~B表示A与B 同构.同构的集合具有相同的基数.对于有限集A和B,判定 它们同构与否是微不足道的.因为这时有:VA,B9, A~B分|A|=|B 812序 对于一个集合M,MxM=(∈R,或xRy.一个序,记为<,就是这样的一 个关系R使得满足如下的三个定律 O1反射律:Vm∈M,cRa, O2反对称律:vx,y∈M,xRy^yRx→x=y O3传递律:V,y,z∈M,cRy∧yRz→cRz 如果一个集合M上带有一个序圣,则称之为偏序集,记为 (M,≤). 定理121对于一个偏序集(M,)Vmx1,x2,…,xn∈M x1x2≤…<xn-x1→x1=x2 (1.21)
6 第一章预备知识 有时,称这个定理为反循环律.如果一个关系只满足O1 和O3但不满足O2,则称它为拟序,记为·<,一个集合M,若 带有一个拟序·<,则称它为拟序集,记为(M,·<) 定理122个拟序集(M,·<)的任何一个子集S本 身也是一个拟序集,其上之拟序为限制在S上的部分 如果在M上的一个拟序E还满足如下的对称律O2,则称 它为一个等价关亲,或简称为等价,记为~ O2对称律:Vx,y∈M,xy→yRx 对于M上的一个等价~.可以定义(M)={y|wy∈ M,y~r称为x在M中的等价类.由M上的所有等价类 构成的集合称为(M,~)的商集,记为M/~.在一个拟序集 M,·<)上,令~<依如下方式的确定:vx,y∈M, <3分(z·<3)∧ 则,容易看出~<是M上的一个等价.而且,(M/~<,·<) 也是一个找序集 定理123个拟序集(M,·<是一个偏序集,当且 仅当M~a=M,或者说它满足反循环律 在一个偏序集(M,≤)中,可以由反反射律 ∈M, 传递律 x<3)A(3<x)→xxz 和 x3分(xy){四=y)