22 第一章预备知识 丌1(P0)=(1),平凡群; 丌(Pp)={a1,b1 bpi Ⅱ),p≥ (1.54) 1≤≤P m(Qg)=(c1s c;cr},q≥1. 这就是说,在P∈P(Qq∈Q)上的任何一类迂(在拓扑学中称 为路)均可由a1,b1…,ap:b(,,…,c)在关系 Ii a, a D=1 II Gc=1 I≤iP <讠< 之下生成,p≥1(g≥1) 个多面形就是多边形的一个集合,记 ∑=(X1,X (15a) 其中多边形X1,…,Xn定义在字母集三上使得每个字母在它们 之中恰出现二次并且没有一个真子集也有这一性质而且,由 ∑出发还可以定义在同样字母集三上的另一个多面形,记 (X1’,X2*,…,Xm") 满足关系:vx,y∈ ysX∈∑→xysX∈Σ 使得任何一个字母的两次出现的幂之积与在Σ中相同.容易 看出,、Σ·=Σ.由此,称∑*为∑的对偶在∑中多边形称
§15曲面 为面,字母称为棱(或边).∑*中的面称为Σ的顶点或节点) 对于多面形∑,称 x(∑)=v-E+φ (1.6) 为它的Eler示性数.其中,v,∈和分别为∑的顶点数,棱 数和面数 如果一个多面形可以通过(5.3)变为另一个使得每一个 字母的二次出现的幂是不同的,则称它为可定向的;否则,不 可定向的 在多面形上,下面所定义的运算3也称为初等变换.可 以看出它是从曲面的情形引伸出来的实际上到0和E2可 以由El3导出 El.3(A≠6VB≠叭) (Aa,a-1B)→(AB) 多面形可以用引伸的等价,也记为~E进行分类.可以证 明任何多面形都与一个曲面等价.而且,可定向性和 Euler示 性数是初等变换下的二个不变量因此,我们有 定理154∑ P,当x(∑)=2,可定向; 当x(2)=2-2p,P>1, 可定向; (1.5.7) Qq,当x(∑)=2-q,q≥ 不可定向
24 第一章预备知识 这个定理可以使我们定义曲面S的Eue"示性数x(S)为 其上多面形的 Euler示性数.并且称(157)为Euer公式 对于分别定义在三1和三2上的二多面形∑1和Σ2如果存 在一个双射r:三1→三2使得VX∈∑1, X=Aa BaC+T(X)=T(Ar(a)r(B)()r(C) ∈S2 则称∑1和∑2是同构的.其中的r为它们之间的一个同构.在 第十章中我们将会看到判定两个多面形同构与否并不是很困 难的 给定一个多面形∑,可以得到一个图G(E)=(V(∑),E(C 其中,V(和E(以)分别为∑的所有顶点的集合和所有棱的集 合.G(以)被称为∑的基准图而,Σ被称为G(E)的准基形 对于一个图G=(VE),如果存在一个多面形Σ~!S∈S使 得G为Σ的基准图,则称G可嵌入到曲面S上,简记G∝S. 这个多面形∑被称为G在S上的一个嵌入,或记为G(以)CS 第十二章将讨论有关图在曲面上的可嵌入性的各种问题 81.6注记 161首先要提到的是关于一个理论的有效性或者好的 标准.我们尽可能使一种理论更有效.所谓一种理论是有效的 指可以借助它设计多项式时间的算法,即计算时间不超过问题 阶的-个多项式在15中所建立的曲面分类的理论就是使之 成为有效的一个实例 162关于算法的设计与分析,Aho, Hopcroft和 Ulman 的书{AHU提供了基础知识.如果必要,读者也可以参见书
816注记 25 末文献中的有关文章 163关于算法复杂性的理论,特别是NP完全性理 论,虽然当今发展的十分迅速即使是初学者, Garey和 Johnson 的书间G仍不乏适用.对于这一理论本身尤感兴趣的读者 也许想读一读Cok和Kap的奠基性的文章Co]和[Kal,关 于这一理论的简述还可查 Hammer,刘彦佩和 Simeone的文章 HLS1]不过,仅适于中文读者 164关于多面形更为精细的定义将在第十章中出现 它形成了组合地图理论的基础{ut19在那一章还提供了两 多面形同构与否的有效识别.当然,全面的理论有待另一本专 著,因为在这方面所取得的结果已丰富多姿
第二章 图中的树 21树与上树 虽然树本身不仅在图论中而且在数学的别的分枝中也是 最简单的而且重要的一个课题.这里不能详细讨论其各个方 面.我们只仅就树作为图的子图以简化对于与各种图的可嵌入 性和确定相应的嵌入有关的问题之处理 树作为一类图在12中已给出了定义,而且,它可以用下 面的说法之一确定,这些说法将会在以后用到 T,1一个连通且无圈的图 T2阶为w度为v-1的连通图 Tr3任何二个节点郗有且仅有一路连它们的图 Tr4任何一个连通子图皆树的连通图 Tr5基本群是平凡群的图 当然,它们都容易被证明.而且,其中一些(就作者之印 象T1-3)可以在任何一本基础图论的教科书中看到,不管 怎样,我们很关心树在础面上的可嵌入性和嵌入