第一章预备知识 定理134一个v阶图是树当且仅当它的度为v-1而 且所有的边皆割边 一个既无孤立点也无割点的图被称为块或者说不可分离 的用12中的O1,O2和O3易见“两条边在一个图上”的说 法是边集上的一个等价,记为~b 定理135个无孤立点的图是不可分离的,当且仅 当|E/~b=1 图G的一个子图H,如果V(H)=V则H是G的一个支 撑子图.G的一个支撑圈称为 Hamilton團.一个支撑回使得 G的每一条边均出现,则称为Eler回.若一个图G有 Hamilton 盟或 Euler回,则分别称它为 Hamilton图或 Euler图 定理136一个图是 Euler图,当且仅当它的节点全是 偶的 对于一个图G若v=A+B(也就是AUB且A∩B=四)且 GA]和G全是孤立图则称G为二部图,记为G=(A,B;E 如果 E={x,v)|(v∈A)(v∈B)} 则称G=(A,B;E)为完全二部图,常记为Ka,,其中a=A 和B=B 定理137一个图是二部图,当且仅当它没有奇长圈 如果v或E的一个子集中的任意二个元素在图G=(V,E 中都是不相邻的,则称这个子集为独立的E的独立子集也称 为对集或匹配.如果一个对集导出一个支撑子图,则称之为
§13图 13 完满的(或完美的).对于a∈V,令 {v∈v, v adj a} 和对于A≤V,记 N(4)=∪N 定理138 个二部图G=(X,Y;E)有一个完美对 集,当且夂当ⅤAsX和ⅤAY,有|N(A)2|Al 已经知道,任何一个图均可在3维欧氏空间中实现,用点 表示节点用曲线(实际上直线也是允许的)所表示边使得任何 二条代表边的线除端点可能公共外(这时二边有公共端点)不 再有任何公共点图的这样一种表示称为它在这个空间上的一 个嵌入,然而,不是所有的图均有在平面上的嵌入.如果有这 种嵌入则称它为可平面的 在一个图G上的一个双分就是其上的这样一个运算使得 G=(VE)变为(V+{o},{E\{(,y)})+{(v,x),(,v)}).自然, 它的逆也是有意义的.如果一个图可以从另一个图经过一系列 的双分而得到,则称它们是同胚的 定理139个图是可平面的,当且仅当它没有子图 与K5或K33同胚 对于二个图G1=(V,E1)和G2=(V2,E2),如果存在一个 双射r:ⅵ→V使得u,U∈Ⅵ, (,v)∈五1兮((u),r(v)∈E2, (1.34) 则称它们是同构的,由(134)所确定的双射r称为G1和G2 间的一个同构.若G1=G2=G,则这时的同构被称为G上的
14 第一章预备知识 自同构.一般而论,在前面曾提到过的问题中,判定两个图同 构与否也许是最困难的 相仿地,可以定义有向图,用D=(v,A)表示,其中V为 节点集,A是一个二元关系使得 A CVxV={<u,υXvt∈ Vv∈V},称为孤集.上面所有的讨论均可相仿地用于有向 图.特别是,任何一个偏序集P=(M;)均可用一个有向图 表示,记为Dos=(M,Aos),其中 <m,y>∈A0s(xy)∧(2,xz1g), 或者说x被y覆盖,m,y∈M.如果一个v阶图伴随一个从它 的节点集到整数集(几乎总是{1,2,…,砂})的单射(双射,则称 它为标定的在标定之下节点的象被称为这个节点的标记当 然,二标定(或有向)图之间的同构必须考虑节点上的标记(边 上的方向) 814群 个群,用F=(X,今)表示,就是一个集合x连同一个二 元关系7XxX→X,也许用2◇y代表<x,xy而将◇视 为运算更方便,使得如下的三条定律r1,r2和r3得到满足 r1(结合律)vm;y,z∈S,(xy)z=x◇(y◇ r2(幺元律)(1r(或简记1)∈S)a∈S,z1r=x r3{逆元律)(x∈S)(y∈S,m◆y=lr) 在T2中的元素1被称为右么元在r3中的y为x的右 逆,相仿地,可以定义左幺无和一个元素的左逆.然,可以证 明它们全是唯一的而且左的与右的相等.因此,我们可以称1 为幺元和x-1为x的逆
§14群 15 个群r=(X,◇)的阶就是|x|可以看出(1,◇)是 个群,称之为平凡群或幺群,在本书中,如无特别说明,总是 用r=X表示群r=(X,◇).如果一个群r还满足下面的r4 则称它为Abe群 r4(交换律)Vx,y∈I,zy=yx 有二种常用方式表示群的运算,一个是加号即用x+y代 替x◇y.这时的幺元为0(或0)x的逆为一x,特别是对于 Abel群而言是这样.另一个就是乘号,即用x·y(或xy)代 替x◇y.这时的幺元为1r(或1),z的逆为x-1.通常以此表 示一般的群 令r=(X,是一个群和Y≤X.若A=(Y,·)也是一个 群,则称A为r的子群,也用A∈I表之.当然,幺群是任何 群的子群.任何一个群均为它本身的子群 定理141W≠Ygx, A=(Y,-)sr=(X,)兮(vm,∈Y)(zy1∈Y) 令I=(X;,·)≤=(X,°),∈I容易看出,它们的交 =(∩xcr i∈I i∈I 对于S∈X,所有包含S的子群的交,用《S}表示,称为r中 由S生成的子群.子群{urX),用Uier;表示,称为子群 r;,∈I,的联.令r为由r的所有子群组成的集合,由312中 的O1-03和定理128易知(rS;U,∩)是一个格,或更确切 地,一个完全格.因为r的任何一个子集在r中既有最小上 界,即其中所有子群的交,又有最大下界,即其中所有子群的 联
16 第一章预备知识 群r的一个子群A,若A满足如下的等价条件之一:Vx∈T, zA=AxV∈I,x-1Ax=A 141) 台va∈I,vy∈A,xgyz∈A, 则称A为r的正规子群,记为A<I 容易看出,一个Abel群的任何子群皆正规.然,一般而 言,对于非Abel群确有子群不是正规的.也可以看出,一个群 的所有正规子群的集形成一个完全格.其中,包含关系为序, 联和交为两个运算 对于NI,=(X,),可以按如下方式确定X上的一个 关系,用~N表示:vam,y∈X, 3∈N,2 (14.2) 容易验证,~N是集合X上的一个等价,由此,可以定义在I 中N的商群为 r/N=(X/~,·) 143) 其中,(Nx)(Ny)=N(xg).商群r/N的阶称为N在r中的指 标 令和A是两个群.一个函数a:r→∧,如果, Va,yE r, aey)= a(e)a(u), (1.44 则称之为从到A的一个同态 由于o:→1A是一个同态,且称之为零同态,从r到A 的所有同态的集合om(T,A)总是非空的.一个群r到它本 身的同态称为它的自同态.幺函数t:I→P就是r的一个自 同态