812序 定义这个序的真包含,用式示,如果M上的序<满足如下 所述的交错律O4,则称它为全序,或者说线性序 O4交错律:V,y∈M,zy→y≤ 带有一个全序的集合被称为链,一个含有n个元素的链 的长度定义为n-1.由定理122和定义,即可得 定理12.4一个偏序集的任何一个子集均为偏序集 而且,任何链的子集仍为链 由定义可知,集合M上的一个关系R的逆为R v,y∈M,xRy分yRx 经过检查O1-03,容易得到 定理125(对偶准则)一个序的逆本身也是一个序 在一个偏序集(M,)中,可以有一个元素a:V∈M,a x根据O2如果这样的元素存在,它必是唯一的.这时,称它 为最小元用O表示,对偶地,最大元,用表示,它们如果 存在,则称为M的遵界 定理120任何有限的链都有通界 在偏序集(M,)中,元素a∈M:v∈M,x-a→x=a 被称为极小元对偶地,极大元,即a∈M:V∈M,a<x→ 定理127任何有限非空的偏序集(M,)都有极小元 和极大元 对于二个偏序集(M,)和(N,),一个映象r:M→N
8 第一章预备知识 如果满足:Vx,3∈M, ≤y兮r(x)-τ(3y), (123) 则称之为保序或者说同序.进而,如果一个同序r:M→N 还满足:vxr,y∈M, r(x)<r(3)→x玉y 124 则称之为同构.两个偏序集(M,-)和(N,)间如果存在一个 同构,则称它们是同构的,记为(M,)坐(N,)所有互相同 构的偏序集被视为相同的.然,一般而论,判定两个偏序集是 否同构并不容易 偏序集(M,)的子集X的上界就是这样的一个元素 vz∈X,x≤a.所谓最小上界(或1ub.)就是这样的上界 b:a≤b→a=b,其中a也是X的一个上界,对偶地可知, 下界和最大下界(g:lb)一个偏序集的长度就是其中链的长 度的最小上界.一个格就是这样的一个偏序集使得它的任何 二个元素x和y都有一个最大下界,称之为下丘并用x^y表 示,和有一个最小上界,称之为上谷并用zVy表示.因此, 常用L=(M,≤;V,A)表示格·如果一个格的所有子集都有 个最大下界和一个最小下界,则称它是完全的 令2为由9的所有子集组成的集合.由11中所讨论的 可知(2,s;U,∩是一个格.实际上,我们有 定理1.28个偏序集是一个格,当且仅当它满足排 中律,交换律,结合律和吸收律 两个格(M,≤;V,八和(N,xV,八被称为同构的如果在两 个偏序集(M,“)和(M,)之间存在一个同构r使得:Vz,y∈ M
513图 (r(arvy)=ra)vr(y))A(r(E Ay =T(x)AT(3) (125 当然,判定二个格是否同构一般而论也不是很容易的 §13图 一个图,用G=(VE)表示,就是一个集合V,称为节点 集,它的元素称为节点,和V上的一个二元关系EV*V= {(u,v)|Vu,v∈V≠t}.称为边集,它的元素称为边.注意, 其中(u,v)=(v,)有时,(u,u)以及在E中重元素也是允许 的.(x,)称为环E的重元素为重边.若V中含有有限个节 点,则称这时的G为有的本书只讨论有限图.记v=|v 被称为G的阶.c=|E|为G的度如果E=V*V,则称G 为完全图,记为K,或统记为K.如果图H=V(H),E(H)) 满足关系V(H)三V和E(H)sE,则称H为G的子图,记为 HsG.容易看出,任何一个图均是同阶或更高阶的完全图之 子图.空图,也记为是任何一个图的子图.没有边的图称为 孤立图.只有一个节点的孤立图称为平凡的,常记为的1 定理131Ⅶv1V,B1<E2 (V1,E1)=G1SG2=(V2,E2) 兮E1<V*V1 (13.1) 与肌1中集合的情形相仿地,也可定义并和交的运算 vG:=(V1,E1),G2=(V,E2)sK G1uG2=(vUv,B∪E2 (1.32)
第一章预备知识 1∩G2=(ⅵnv,E1∩E2) (133) 容易证明(2K,c),2K为K的所有子图的集合,是一个偏序集 而且对于u和∩满足排中律、交换律、结合律和吸收律.因 此,由定理128,(2X,s;∪,∩)形成一个格 对于任一边e=(,v)∈E,它的两个端点被称为相的 或简记 a adi u.同时,e与u或v关联,简记“eind”或“eind 反之,或v也称为与e关联,即 u ind e 或 o ind e 每 条边均可视为由两条半边组成:它们被记为{,v和(x,v分 别不与u和v关联前与v和u关联一个节点v的次或价是 指与v关联半边的数目,记为p(v).如果p(u)=1(mod2),称v 为奇节点;否则,偶节点.次为k,k≥0,的节点也称k次节点 或k节点一个0节点被称为孤立点1-节点也称为显节点 定理132在任一图中,奇节点的数目恒为偶数 如果图G的一个子图H满足 E(H)={(u,v)1u,∈v(H,(uv)∈E} 则称H为G的节点导出子图,G的一个子图H,若v(H {v|e∈E(H), v ind e},则称H为G的边导出子图.常用 Gv(H)和GE(H)分别表示G的节点和边导出子图,可以看 出:VH∈G, H=G{v(H)台∈V(H), (a,U)∈E\E(H)) 和YHG, H=G[E(以分(∈v(F)(PH()=0)
§1.3图 11 令2;和2分别为G中的所有节点和边导出子图的集 合.容易用12中的O1-03验证(2G,g)和(2,g)皆偏 序集.进而,(201,g)和(2,g)也都可视为格.不过,这 时并和交在它们之中一般不是封闭的 在图G中,两个节点u,之间的迹或遼径,用Tr(u,v)表 示,即这样的一个边的序列e1,e2,,et使得e;=(v;,v+1),t= 1,2,…,1,=u1,=w+1.其中的l被称为长度.若一个迹 Tr(u,v)的二端u=v,则称它为闭迹,或迂,记为Tr(a),或简写 n如果一个迹中的所有边没有相同的,则称它为游或径,记 为Tr(u,v).当u=v时,Tr(a,v)被称为闭游,或回,记为Tr(a), 或T.如果一个游T{v,v)的边导出子图H=GE(T(u,)满 足条件 (pr(x)=p(u)=1)∧(pH(v)=2,=1,2,…,t-1), 则称它为路,常记为P(u,0,或P.闭路被称为圈,常记为C(a), 或C.当然,游和路都是边导出子图.两个节点称为是连通的 即指在图中存在连它们的一条路.如果G中任何二个节点是 连通的,则称G本身是连通的.用1.2中的O1,O2和O3容 易验证两点之间的连通性是V上的一个等价,用~表示 定理133图G=(V,E)是连通的,当且仅当v/~c=1 令σ叫Ⅳ/~小称a为G的连通片数(或分图数)对于 一个节点v,记G-v=(\{},E\E),其中,E={elve∈ E, e ind v}如果节点v满足o(G-v)>a:则称它为割点相仿 地,割边为使得σ(G-e)>σ的边e.其中,G-e=(V,E{e}) 一个树就是度最小的连通图.可以证明,所有v阶树的度均 为ν