离散数学复习华师计算机学院PPT课件

1、1第三部分 代数结构 主要内容l 代数系统: 二元运算及其性质、代数系统和子代数l 半群与群: 半群、独异点、群l 环与域: 环、整环、域第1页/共76页2第九章 代数系统 主要内容 二元运算及其性质l 一元和二元运算定义及其实例l 二元运算的性质 代数系统l 代数系统定义及其实例l 子代数l 积代数 代数系统的同态与同构第2页/共76页3基本要求l 判断给定集合和运算能否构成代数系统l 判断给定二元运算的性质l 求而二元运算的特异元素l 了解同类型和同种代数系统的概念l 了解子代数的基本概念l 计算积代数l 判断函数是否为同态映射和同构映射第3页/共76页4一、二元运算及其性质 定义9.1

2、设S为集合，函数f：SSS 称为S上的二元运算，简 称为二元运算l S中任何两个元素都可以进行运算，且运算的结果惟一l S中任何两个元素的运算结果都属于S，即S对该运算封闭 定义9.2 设S为集合，函数 f:SS 称为S上的一元运算，简 称一元运算. 第4页/共76页5二元运算的性质 定义9.3 设为S上的二元运算, (1) 若对任意x,yS 有 xy=yx, 则称运算在S上满足交换律. (2) 若对任意x,y,zS有 (xy)z=x(yz), 则称运算在S上满足结 合律. (3) 若对任意xS 有 xx=x, 则称运算在S上满足幂等律.定义9.4 设和 为S上两个不同的二元运算, (1) 若

3、对任意x,y,zS有 (x y)z=(xz) (yz)， z(x y)=(zx) (zy), 则称运算对 运算满足分配律. (2) 若 和 都可交换,且对任意x,yS有 x(x y)=x，x (xy)=x, 则称和 运算满足吸收律. 第5页/共76页6特异元素：单位元、零元 定义9.5 设为S上的二元运算, (1) 如果存在el (或er)S，使得对任意 xS 都有 elx = x (或 xer = x)， 则称el (或er)是S中关于运算的左(或右)单位元. 若eS关于运算既是左单位元又是右单位元，则称e为S上 关于运算的单位元. 单位元也叫做幺元. (2) 如果存在 l (或 r)S，使

4、得对任意 xS 都有 l x = l (或 x r = r)， 则称 l (或 r)是S 中关于运算的左(或右)零元. 若 S 关于运算既是左零元又是右零元，则称为S上关 于运算的零元.第6页/共76页7可逆元素和逆元 (3) 设为S上的二元运算, 令e为S中关于运算的单位元. 对于xS，如果存在yl (或yr)S使得 ylx=e（或xyr=e） 则称yl (或 yr)是x的左逆元（或右逆元）. 关于运算，若yS 既是 x 的左逆元又是 x 的右逆元，则称 y为x的逆元. 如果 x 的逆元存在，就称 x 是可逆的.第7页/共76页8惟一性定理 定理9.1 设为S上的二元运算，el和er分别为S

5、中关于运算的 左和右单位元，则el = er = e为S上关于运算的惟一的单位元. 类似地可以证明关于零元的惟一性定理. 注意：l 当 |S| 2，单位元与零元是不同的；l 当 |S| = 1时，这个元素既是单位元也是零元. 定理9.2 设为S上可结合的二元运算, e为该运算的单位元, 对于xS 如果存在左逆元 yl 和右逆元 yr, 则有 yl = yr= y, 且 y 是 x 的惟一的逆元.第8页/共76页99.2 代数系统 定义9.6 非空集合S和S上k个一元或二元运算f1, f2, fk组成 的系统称为代数系统, 简称代数，记做. 构成代数系统的成分：l 集合（也叫载体，规定了参与运算

6、的元素）l 运算（这里只讨论有限个二元和一元运算）l 代数常数（通常是与运算相关的特异元素：如单位元等） 研究代数系统时，如果把运算具有它的特异元素也作为系统 的性质之一，那么这些特异元素可以作为系统的成分，叫做 代数常数. 第9页/共76页10子代数系统 定义9.8设V=是代数系统，B是S的非空子 集，如果B对f1, f2, , fk 都是封闭的，且B和S含有相同的代 数常数，则称是V的子代数系统，简称子代 数. 有时将子代数系统简记为B.说明：l 子代数和原代数是同种的代数系统l 对于任何代数系统V=，其子代数一定存在. 第10页/共76页11第十章 群与环 主要内容l 群的定义与性质l

7、子群与群的陪集分解l 循环群与置换群l 环与域第11页/共76页12基本要求l 判断或证明给定集合和运算是否构成半群、独异点和群l 熟悉群的基本性质l 能够证明G的子集构成G的子群l 熟悉陪集的定义和性质l 熟悉拉格朗日定理及其推论，学习简单应用l 会求循环群的生成元及其子群l 熟悉n元置换的表示方法、乘法以及n元置换群l 能判断给定代数系统是否为环和域 第12页/共76页13l 半群、独异点与群的定义l 半群、独异点、群的实例l 群中的术语l 群的基本性质10.1 群的定义与性质第13页/共76页14半群、独异点与群的定义 定义10.1 (1) 设V=是代数系统， 为二元运算，如果 运算是可

8、 结合的，则称V为半群. (2) 设V=是半群，若eS是关于 运算的单位元，则称V 是含幺半群，也叫做独异点. 有时也将独异点V 记作 V=. (3) 设V=是独异点，eS关于 运算的单位元，若 aS，a1S，则称V是群. 通常将群记作G. 第14页/共76页15有关群的术语 定义10.2 (1) 若群G是有穷集，则称G是有限群，否则称为无 限群. 群G 的基数称为群 G 的阶，有限群G的阶记作|G|. (2) 只含单位元的群称为平凡群. (3) 若群G中的二元运算是可交换的，则称G为交换群或阿贝 尔 (Abel) 群.定义10.4 设G是群，aG，使得等式 ak=e 成立的最小正整数k 称为

9、a 的阶，记作|a|=k，称 a 为 k 阶元. 若不存在这样的正整数 k，则称 a 为无限阶元.第15页/共76页16群的性质：幂运算规则 定理10.1 设G 为群，则G中的幂运算满足： (1) aG，(a1)1=a (2) a,bG，(ab)1=b1a1 (3) aG，anam = an+m，n, mZ (4) aG，(an)m = anm，n, mZ (5) 若G为交换群，则 (ab)n = anbn.第16页/共76页17群的性质：消去律；元素的阶 定理10.3 G为群，则G中适合消去律，即对任意a,b,cG 有 (1) 若 ab = ac，则 b = c. (2) 若 ba = ca

10、，则 b = c. 例例 5 设设G是群，是群，a,bG是有限阶元是有限阶元. 证明证明 (1) |b 1ab| = |a| (2) |ab| = |ba|定理10.4 G为群，aG且 |a| = r. 设k是整数，则 (1) ak = e当且仅当r | k (2 )|a 1| = |a|第17页/共76页1810.2 子群与群的陪集分解 定义10.5 设G是群，H是G的非空子集， (1) 如果H关于G中的运算构成群，则称H是G的子群, 记作HG. (2) 若H是G的子群，且HG，则称H是G的真子群，记作HG.例如 nZ (n是自然数) 是整数加群 的子群. 当n1时,nZ是Z的真子群.对任何

11、群G都存在子群. G和e都是G的子群，称为G的平凡子群. 第18页/共76页19子群判定定理 定理10.5（判定定理一） 设G为群，H是G的非空子集，则H是G的子群当且仅当 (1) a,bH有abH (2) aH有a1H.定理定理10.6 （判定定理二）（判定定理二）设设G为群，为群，H是是G的非空子集的非空子集. H是是G的子群当且仅当的子群当且仅当 a,bH有有ab 1H. 定理定理10.7 （判定定理三）（判定定理三） 设设G为群，为群，H是是G的的非空非空有穷子集，则有穷子集，则H是是G的子群当且仅当的子群当且仅当 a,bH有有abH. 第19页/共76页20典型子群的实例定义10.6

12、 设G为群，aG，令H=ak| kZ，则H是G的子群，称为由 a 生成的子群，记作.定义定义10.7 设设G为群为群,令令 C=a| aG xG(ax=xa)，则则C是是G的子群，称为的子群，称为G的的中心中心. 例例6 设设G是群，是群，H,K是是G的子群的子群. 证明证明(1) HK也是也是G的子群的子群(2) HK是是G的子群当且仅当的子群当且仅当 H K 或或 K H第20页/共76页21陪集 定义10.9 设H是G的子群，aG.令Ha=ha | hH 称Ha是子群H在G中的右陪集. 称a为Ha的代表元素. 定理定理10.8 设设H是群是群G的子群，则的子群，则 (1) He = H(

13、2) aG 有有aHa定理定理10.9 设设H是群是群G的子群，则的子群，则 a,bG有有 aHb ab 1H Ha=Hb第21页/共76页22推论 推论 设H是群G的子群, 则 (1) a,bG，Ha = Hb 或 HaHb = (2) Ha | aG = G 证明：由等价类性质可得. 定理定理10.10 设设H是群是群G的子群，在的子群，在G上定义二元关系上定义二元关系R： a,bG, R ab 1H则则 R是是G上的等价关系，且上的等价关系，且aR = Ha.第22页/共76页23左陪集的定义与性质 设G是群，H是G的子群，H 的左陪集，即aH = ah | hH，aG 关于左陪集有下述

14、性质： (1) eH = H (2) aG，aaH (3) a,bG，abH b1aH aH=bH (4) 若在G上定义二元关系R， a,bG，R b1aH 则R是G上的等价关系，且aR = aH. (5) aG，H aH 第23页/共76页24Lagrange定理 定理10.12 （Lagrange）设G是有限群，H是G的子群，则 |G| = |H|G:H 其中G:H 是H在G中的不同右陪集(或左陪集) 数，称为H在 G 中的指数. 推论1 设G是n阶群，则 aG，|a|是n的因子，且有an = e.推论2 对阶为素数的群G，必存在aG使得G = . 第24页/共76页25Lagrange定

15、理的应用 命题：如果群 G 只含 1 阶和 2 阶元，则 G 是Abel群. 例8 证明 6 阶群中必含有 3 阶元. 证 设a为G中任意元素，有a 1 = a. 任取 x, yG，则 xy = (xy) 1 = y 1x 1 = yx， 因此G是Abel群. 证 设G是6 阶群，则G中元素只能是1阶、2阶、3阶或6阶.若G中含有6 阶元，设为a，则 a2是3 阶元. 若G中不含6 阶元，下面证明G中必含有3阶元. 如若不然，G中只含1阶和2阶元，即 aG，有a2=e，由命题知G是Abel群. 取G中2阶元 a 和 b，a b，令 H = e, a, b, ab，则H 是 G的子群，但 |H|

16、 = 4，|G| = 6，与拉格朗日定理矛盾. 第25页/共76页2610.3 循环群与置换群 定义10.10 设G是群，若存在aG使得 G=ak| kZ 则称G是循环群，记作G=，称 a 为G 的生成元. 循环群的分类：n 阶循环群和无限循环群. 设G=是循环群，若a是n 阶元，则 G = a0=e, a1, a2, , an 1 那么|G| = n，称 G 为 n 阶循环群. 若a 是无限阶元，则 G = a0=e, a1, a2, 称 G 为无限循环群. 第26页/共76页27循环群的生成元 定理10.13 设G=是循环群. (1) 若G是无限循环群，则G只有两个生成元，即a和a1. (

17、2) 若G是 n 阶循环群，则G含有(n)个生成元. 对于任何小 于n且与 n 互质的数r0,1,n-1, ar是G的生成元.(n)成为欧拉函数，例如 n=12，小于或等于12且与12互素的 正整数有4个： 1, 5, 7, 11， 所以(12)=4.第27页/共76页28循环群的子群 定理10.14 设G=是循环群. (1) 设G=是循环群，则G的子群仍是循环群. (2) 若G=是无限循环群，则G的子群除e以外都是无限 循环群. (3) 若G=是n阶循环群，则对n的每个正因子d，G恰好含 有一个d 阶子群.第28页/共76页2910.4 环与域 定义10.12 设是代数系统，+和是二元运算.

18、 如果满足 以下条件: (1) 构成交换群 (2) 构成半群 (3) 运算关于+运算适合分配律 则称是一个环. 通常称+运算为环中的加法，运算为环中的乘法. 环中加法单位元记作 0，乘法单位元（如果存在）记作1. 对任何元素 x，称 x 的加法逆元为负元，记作x. 若 x 存在乘法逆元的话，则称之为逆元，记作x1. 第29页/共76页30定理10.16 设是环，则 (1) aR，a0 = 0a = 0(2) a,bR，( a)b = a( b) = ab(3) a,b,cR，a(b c) = ab ac， (b c)a = ba ca(4) a1,a2,.,an,b1,b2,.,bmR (n,

19、m2) babajnimjimjjnii 1111)()(环的运算性质 第30页/共76页31特殊的环 定义10.13 设是环 (1) 若环中乘法 适合交换律，则称R是交换环 (2) 若环中乘法 存在单位元，则称R是含幺环 (3) 若a,bR，ab=0 a=0b=0，则称R是无零因子环 (4) 若R既是交换环、含幺环、无零因子环，则称R是整环 (5) 设R是整环，且R中至少含有两个元素. 若aR*，其中 R*=R0，都有a1R，则称R是域.第31页/共76页32第五部分 图论本部分主要内容l 图的基本概念l 欧拉图、哈密顿图l 树l 平面图l 支配集、覆盖集、独立集、匹配与着色第32页/共76

20、页33第十四章 图的基本概念 主要内容l 图l 通路与回路l 图的连通性l 图的矩阵表示l 图的运算 预备知识l 多重集合元素可以重复出现的集合l 无序集AB=(x,y) | xAyB第33页/共76页34基本要求l 深刻理解握手定理及推论的内容并能灵活地应用它们l 深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图的概念以及它们的性质及相互之间的关系l 记住通路与回路的定义、分类及表示法l 深刻理解与无向图连通性、连通度有关的诸多概念l 会判别有向图连通性的类型l 熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法，会求可达矩阵 第34页/共76页35相关概念1. 图 可用G泛指图

21、（无向的或有向的） V(G), E(G), V(D), E(D) n阶图2. 有限图3. n 阶零图与平凡图（1阶零图）4. 空图5. 用 ek 表示无向边或有向边6. 顶点与边的关联关系 关联、关联次数 环 孤立点7. 顶点之间的相邻与邻接关系第35页/共76页36多重图与简单图 定义14.3 (1) 无向图中的平行边（大于1条）及重数 (2) 有向图中的平行边及重数（注意方向性） (3) 多重图（含平行边的图） (4) 简单图（既不含边，也不含环的图） 在定义14.3中定义的简单图是极其重要的概念 第36页/共76页37顶点的度数定义14.4 (1) 设G=为无向图, vV, d(v)v的

22、度数, 简称度 (2) 设D=为有向图, vV, d+(v)v的出度 d(v)v的入度 d(v)v的度或度数 (3) (G), (G) (4) +(D), +(D), (D), (D), (D), (D) (5) 奇顶点度与偶度顶点第37页/共76页38mvdnii2)(1 mvdvdmvdniiniinii 111)()(,2)(且且定理定理14.1 设设G=为任意无向图，为任意无向图，V=v1,v2,vn, |E|=m, 则则推论 任何图 (无向或有向) 中，奇度顶点的个数是偶数.握手定理定理14.2 设D=为任意有向图，V=v1,v2,vn, |E|=m, 则第38页/共76页39图的度

23、数列1 . V=v1, v2, , vn为无向图G的顶点集，称d(v1), d(v2), , d(vn)为G的度数列 2. V=v1, v2, , vn为有向图D的顶点集， D的度数列：d(v1), d(v2), , d(vn) D的出度列：d+(v1), d+(v2), , d+(vn) D的入度列：d(v1), d(v2), , d(vn) 3. 非负整数列d=(d1, d2, , dn)是可图化的，是可简单图化的.易知：(2, 4, 6, 8, 10)，(1, 3, 3, 3, 4) 是可图化的，后者又是可简单图化的，而(2, 2, 3, 4, 5)，(3, 3, 3, 4) 都不是可简

24、单图化的，特别是后者也不是可图化的第39页/共76页40n 阶完全图与竞赛图 定义14.6 (1) n (n1) 阶无向完全图每个顶点与其余顶点均相邻的无向简单图，记作 Kn. 简单性质：边数 (2) n (n1)阶有向完全图每对顶点之间均有两条方向相反的有向边的有向简单图. 简单性质： (3) n (n1) 阶竞赛图基图为Kn的有向简单图. 简单性质：边数1,2)1( nnnm 1),1(2),1( nnnnm 1,2)1( nnnm 第40页/共76页41子图 定义14.8 G=, G= (1) GG G为G的子图，G为G的母图 (2) 若GG且V=V，则称G为G的生成子图 (3) 若VV

25、或EE，称G为G的真子图 (4) V（VV且V）的导出子图，记作GV (5) E（EE且E）的导出子图，记作GE第41页/共76页42补图定义14.9 设G=为n阶无向简单图，以V为顶点集，以所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作 .若G , 则称G是自补图. GG第42页/共76页4314.2 通路与回路定义14.11 给定图G=（无向或有向的），G中顶点与边的交替序列 = v0e1v1e2elvl，vi1, vi 是 ei 的端点.(1) 通路与回路： 为通路；若 v0=vl， 为回路，l 为回路长 度.(2) 简单通路与回路：所有边各异， 为简单通路，又若

26、v0=vl， 为简单回路(3) 初级通路(路径)与初级回路(圈)： 中所有顶点各异，则称 为初级通路(路径)，又若除v0=vl，所有的顶点各不相同且所有的边各异，则称 为初级回路(圈)(4) 复杂通路与回路：有边重复出现第43页/共76页44通路与回路的长度 定理14.5 在n 阶图G中，若从顶点vi 到vj（vivj）存在通路， 则从vi 到 vj 存在长度小于或等于n1 的通路. 推论 在 n 阶图G中，若从顶点vi 到 vj（vivj）存在通路，则 从vi 到vj 存在长度小于或等于n1的初级通路（路径）. 定理14.6 在一个n 阶图G中，若存在 vi 到自身的回路，则一 定存在vi

27、到自身长度小于或等于 n 的回路. 推论 在一个n 阶图G中，若存在 vi 到自身的简单回路，则一 定存在长度小于或等于n 的初级回路.第44页/共76页4514.3 图的连通性无向图的连通性(1) 顶点之间的连通关系：G=为无向图 若 vi 与 vj 之间有通路，则 vivj 是V上的等价关系 R=| u,v V且uv (2) G的连通性与连通分支 若u,vV，uv，则称G连通 V/R=V1,V2,Vk，称GV1, GV2, ,GVk为连通分 支，其个数 p(G)=k (k1)； k=1，G连通第45页/共76页46无向图的连通度1. 删除顶点及删除边 Gv 从G中将v及关联的边去掉 GV从

28、G中删除V中所有的顶点 Ge 将e从G中去掉 GE删除E中所有边 2. 点割集与边割集 点割集与割点定义14.16 G=, VV V为点割集p(GV)p(G)且有极小性 v为割点v为点割集定义14.17 G=, EE E是边割集p(GE)p(G)且有极小性 e是割边（桥）e为边割集第46页/共76页47有向图的连通性 定义14.20 D=为有向图 vi vj（vi 可达 vj）vi 到vj 有通路 vi vj（vi 与vj 相互可达） 性质 具有自反性(vi vi)、传递性 具有自反性、对称性、传递性 vi 到vj 的短程线与距离 类似于无向图中，只需注意距离表示法的不同 (无向图中d(vi,

29、vj)，有向图中d) 及 d无对称性第47页/共76页48有向图的连通性及分类 定义14.22 D=为有向图 D弱连通(连通)基图为无向连通图 D单向连通vi,vjV，vivj 或 vjvi D强连通vi,vjV，vivj 易知，强连通单向连通弱连通 判别法 定理14.8 D强连通当且仅当D中存在经过每个顶点至少一次 的回路 定理14.9 D单向连通当且仅当D中存在经过每个顶点至少一 次的通路第48页/共76页49二部图定义14.23 设 G=为一个无向图，若能将 V分成 V1和V2(V1V2=V，V1V2=)，使得 G 中的每条边的两个端点都是一个属于V1，另一个属于V2，则称 G 为二部图

30、 ( 或称二分图、偶图等 )，称V1和V2为互补顶点子集，常将二部图G记为. 又若G是简单二部图，V1中每个顶点均与V2中所有的顶点相邻，则称G为完全二部图，记为 Kr,s，其中r=|V1|，s=|V2|. 注意，n 阶零图为二部图. 第49页/共76页50有向图的邻接矩阵（无限制）定义14.26 设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令为顶点 vi 邻接到顶点 vj 边的条数，称为D的邻接矩阵，记作A(D)，或简记为A. 性质 的回路数的回路数中长度为中长度为的通路数的通路数中长度为中长度为1)4(1)3(,.,2 , 1),()2(,.,2 , 1

31、),()1(1)1(,)1(1)1(1)1(DaDmanjvdanivdaniiijiijjniijinjij 第50页/共76页51推论 设Bl=A+A2+Al（l 1），则 Bl中元素为D中长度为 l 的通路总数，)(lija)(liia ninjlija11)( niliia1)( ninjlijb11)( niliib1)(定理14.11 设 A为有向图 D 的邻接矩阵，V=v1, v2, , vn为顶点集，则 A 的 l 次幂 Al（l 1）中元素为D中vi 到vj长度为 l 的通路数，其中为vi到自身长度为 l 的回路数，而为D中长度小于或等于 l 的回路数为D中长度小于或等于 l

32、 的通路数. 邻接矩阵的应用为D 中长度为 l 的回路总数. 第51页/共76页52 否否则则可可达达, 1, 0jiijvvp 1101110111110001P定义14.27 设D=为有向图. V=v1, v2, , vn, 令 有向图的可达矩阵（无限制）称 (pij)n n 为D的可达矩阵，记作P(D)，简记为P. 由于 vi V，vivi，所以P(D)主对角线上的元素全为1. 由定义不难看出, D 强连通当且仅当 P(D)为全1矩阵. 下图所示有向图 D 的可达矩阵为第52页/共76页53第十五章 欧拉图与哈密顿图 主要内容l 欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法l 哈密顿通

33、路、哈密顿回路、哈密顿图、半哈密顿图l 带权图、货郎担问题第53页/共76页54基本要求 基本要求l 深刻理解欧拉图、半欧拉图的定义及判别定理l 深刻理解哈密顿图、半哈密顿图的定义. l 会用哈密顿图的必要条件判断某些图不是哈密顿图. l 会用充分条件判断某些图是哈密顿图. 要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要条件. 第54页/共76页55欧拉图定义 定义15.1 (1) 欧拉通路经过图中每条边一次且仅一次行遍所有顶点的通路. (2) 欧拉回路经过图中每条边一次且仅一次行遍所有顶点的回路. (3) 欧拉图具有欧拉回路的图. (4) 半欧拉图具有欧拉通路而无欧拉回路

34、的图. 几点说明： 规定平凡图为欧拉图. 欧拉通路是生成的简单通路，欧拉回路是生成的简单回路. 环不影响图的欧拉性.第55页/共76页56无向欧拉图的判别法 定理15.1 无向图G是欧拉图当且仅当G连通且无奇度数顶点. 定理15.2 无向图G是半欧拉图当且仅当G 连通且恰有两个奇 度顶点.第56页/共76页57有向欧拉图的判别法 定理15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶 点的入度都等于出度. 定理15.4 有向图D是半欧拉图当且仅当D是单向连通的，且 D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个 的出度比入度大1，而其余顶点的入度都等于出度. 定理15.5 G是非平

35、凡的欧拉图当且仅当G是连通的且为若干 个边不重的圈之并. 第57页/共76页58哈密顿图与半哈密顿图 定义15.2 (1) 哈密顿通路经过图中所有顶点一次仅一次的通路. (2) 哈密顿回路经过图中所有顶点一次仅一次的回路. (3) 哈密顿图具有哈密顿回路的图. (4) 半哈密顿图具有哈密顿通路且无哈密顿回路的图. 几点说明： 平凡图是哈密顿图. 哈密顿通路是初级通路，哈密顿回路是初级回路. 环与平行边不影响哈密顿性. 哈密顿图的实质是能将图中的所有顶点排在同一个圈上第58页/共76页59无向哈密顿图的一个必要条件 定理15.6 设无向图G=是哈密顿图，对于任意V1V且 V1，均有 p(GV1)

36、 |V1|推论 设无向图G=是半哈密顿图，对于任意的V1 V且V1均有 p(G V1) |V1|+1第59页/共76页60无向哈密顿图的一个充分条件 定理15.7 设G是n阶无向简单图，若对于任意不相邻的顶点vi,vj，均有 d(vi)+d(vj) n1 () 则G 中存在哈密顿通路. 推论 设G为n (n3) 阶无向简单图，若对于G中任意两个 不相邻的顶点vi,vj，均有 d(vi)+d(vj) n （） 则G中存在哈密顿回路，从而G为哈密顿图.第60页/共76页61第十六章 树 主要内容l 无向树及其性质l 生成树、最小生成树、基本回路系统、基本割集系统l 根树及其分类、最优树、最佳前缀码

37、、波兰符号法、逆波兰符号法第61页/共76页62基本要求 基本要求l 深刻理解无向树的定义及性质l 熟练地求解无向树l 准确地求出给定带权连通图的最小生成树l 深刻理解基本回路、基本割集的概念，并会计算l 理解根树及其分类等概念l 会画n阶（n较小）非同构的无向树及根树（1n6）l 熟练掌握求最优树及最佳前缀码的方法l 掌握波兰符号法与逆波兰符号法第62页/共76页6316.1 无向树及其性质定义16.1 (1) 无向树连通无回路的无向图(2) 平凡树平凡图(3) 森林至少由两个连通分支（每个都是树）组成(4) 树叶1度顶点(5) 分支点度数2的顶点 第63页/共76页64无向树的等价定义 定

38、理16.1 设G=是n阶m条边的无向图，则下面各命题 是等价的： (1) G 是树 (2) G 中任意两个顶点之间存在惟一的路径. (3) G 中无回路且 m=n1. (4) G 是连通的且 m=n1. (5) G 是连通的且 G 中任何边均为桥. (6) G 中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的圈. 定理16.2 设T是n阶非平凡的无向树，则T 中至少有两片树叶. 第64页/共76页65不一定连通，也不一定不含回路，如图所示不一定连通，也不一定不含回路，如图所示T定义16.2 设G为无向图(1) G的树T 是G 的子图并且是树(2) G的生成树T

39、 是G 的生成子图并且是树(3) 生成树T的树枝T 中的边(4) 生成树T的弦不在T 中的边(5) 生成树T的余树 全体弦组成的集合的导出子图T16.2 生成树第65页/共76页66推论2 的边数为m n+1. T推论3 为G的生成树T的余树，C为G中任意一个圈，则C与 一定有公共边. .证 否则，C中的边全在T中，这与T为树矛盾. TT定理16.3 无向图G具有生成树当且仅当G连通.生成树存在条件推论1 G为n阶m条边的无向连通图，则m n 1. 证 必要性显然.充分性用破圈法（注意：在圈上删除任何一条边，不破坏连通性）第66页/共76页67基本回路系统定理16.4 设T为G的生成树，e为T

40、的任意一条弦，则Te中含一个只有一条弦其余边均为T的树枝的圈. 不同的弦对应的圈也不同. 定义16.3 设T是n阶m条边的无向连通图G的一棵生成树，设e 1, e 2, , e m n+1为T 的弦. 设Cr为T 添加弦e r 产生的只含弦e r、其余边均为树枝的圈. 称Cr为G的对应树T 的弦e r的基本回路或基本圈，r=1, 2, , m n+1. 并称C1, C2, ,Cm n+1为G对应T 的基本回路系统，称m n+1为G的圈秩，记作 (G). 第67页/共76页68基本割集的存在 定理16.5 设T是连通图G的一棵生成树，e为T的树枝，则G 中存在只含树枝e，其余边都是弦的割集，且不

41、同的树枝对 应的割集也不同.定义定义16.4 设设T是是n阶连通图阶连通图G的一棵生成树，的一棵生成树，e 1, e 2, , e n 1为为T 的树枝，的树枝，Si是是G的只含树枝的只含树枝e i的割集，则称的割集，则称Si为为G的对应的对应于生成树于生成树T由树枝由树枝e i生成的生成的基本割集基本割集，i=1, 2, , n 1. 并称并称S1,S2, , Sn 1为为G 对应对应T 的的基本割集系统基本割集系统，称，称n 1为为G的的割割集秩集秩，记作，记作 (G). 第68页/共76页69最小生成树定义16.5 T是G=的生成树(1) W(T)T各边权之和(2) 最小生成树G的所有生成树中权最小的求最小生成树的一个算法避圈法（Kruskal）设G=，将G中非环边按权从小到大排序：e1,