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

1大概(dàgài)的考试题型选择题20填空题30计算(jìsuàn)〔简答〕题20证明题30第一页，共77页。12第三局部(júbù)代数结构主要内容代数(dàishù)系统:二元运算及其性质、代数(dàishù)系统和子代数(dàishù)半群与群:半群、独异点、群环与域:环、整环、域第二页，共77页。23第九章代数(dàishù)系统主要内容二元运算及其性质一元和二元运算定义及其实例(shílì)二元运算的性质代数系统代数系统定义及其实例(shílì)子代数积代数代数系统的同态与同构第三页，共77页。34根本(gēnběn)要求判断给定集合和运算能否构成代数系统判断给定二元运算的性质求而二元运算的特异元素了解同类型(lèixíng)和同种代数系统的概念了解子代数的根本概念计算积代数判断函数是否为同态映射和同构映射第四页，共77页。45一、二元运算(yùnsuàn)及其性质设S为集合，函数f：SSS称为(chēnɡwéi)S上的二元运算，简称为(chēnɡwéi)二元运算．S中任何两个元素都可以进行运算，且运算的结果惟一．S中任何两个元素的运算结果都属于S，即S对该运算封闭．设S为集合，函数f:S→S称为(chēnɡwéi)S上的一元运算，简称一元运算.第五页，共77页。56二元运算(yùnsuàn)的性质设◦为S上的二元运算,(1)假设对任意x,y∈S有x◦y=y◦x,那么(nàme)称运算在S上满足交换律.(2)假设对任意x,y,z∈S有(x◦y)◦z=x◦(y◦z),那么(nàme)称运算在S上满足结合律.(3)假设对任意x∈S有x◦x=x,那么(nàme)称运算在S上满足幂等律.定义设◦和∗为S上两个不同的二元运算,(1)假设对任意x,y,z∈S有(x∗y)◦z=(x◦z)∗(y◦z)，z◦(x∗y)=(z◦x)∗(z◦y),那么称◦运算对∗运算满足分配律.(2)假设和∗都可交换(jiāohuàn),且对任意x,y∈S有x◦(x∗y)=x，x∗(x◦y)=x,那么称◦和∗运算满足吸收律.第六页，共77页。67特异(tèyì)元素：单位元、零元设◦为S上的二元运算,(1)如果存在(cúnzài)el(或er)S，使得对任意x∈S都有el◦x=x(或x◦er=x)，那么称el(或er)是S中关于◦运算的左(或右)单位元.假设e∈S关于◦运算既是左单位元又是右单位元，那么称e为S上关于◦运算的单位元.单位元也叫做幺元.(2)如果存在(cúnzài)l(或r)∈S，使得对任意x∈S都有l◦x=l(或x◦r=r)，那么称l(或r)是S中关于◦运算的左(或右)零元.假设∈S关于◦运算既是左零元又是右零元，那么称为S上关于运算◦的零元.第七页，共77页。78可逆元素(yuánsù)和逆元(3)设◦为S上的二元运算,令e为S中关于运算的单位元.对于x∈S，如果存在(cúnzài)yl(或yr)∈S使得yl◦x=e〔或x◦yr=e〕那么称yl(或yr)是x的左逆元〔或右逆元〕.关于◦运算，假设y∈S既是x的左逆元又是x的右逆元，那么称y为x的逆元.如果x的逆元存在(cúnzài)，就称x是可逆的.第八页，共77页。89惟一(wéiyī)性定理设◦为S上的二元运算，el和er分别为S中关于运算的左和右单位元，那么el=er=e为S上关于◦运算的惟一的单位元.类似地可以(kěyǐ)证明关于零元的惟一性定理.注意：当|S|2，单位元与零元是不同的；当|S|=1时，这个元素既是单位元也是零元.设◦为S上可结合的二元运算,e为该运算的单位元,对于x∈S如果存在左逆元yl和右逆元yr,那么有yl=yr=y,且y是x的惟一的逆元.第九页，共77页。9109.2代数(dàishù)系统非空集合S和S上k个一元或二元运算f1,f2,…,fk组成的系统称为代数系统,简称代数，记做<S,f1,f2,…,fk>.构成代数系统的成分：集合〔也叫载体，规定(guīdìng)了参与运算的元素〕运算〔这里只讨论有限个二元和一元运算〕代数常数〔通常是与运算相关的特异元素：如单位元等〕研究代数系统时，如果把运算具有它的特异元素也作为系统的性质之一，那么这些特异元素可以作为系统的成分，叫做代数常数.第十页，共77页。1011子代数系统(xìtǒng)设V=<S,f1,f2,…,fk>是代数系统，B是S的非空子集，如果B对f1,f2,…,fk都是封闭的，且B和S含有(hányǒu)相同的代数常数，那么称<B,f1,f2,…,fk>是V的子代数系统，简称子代数.有时将子代数系统简记为B.说明：子代数和原代数是同种的代数系统对于任何(rènhé)代数系统V=<S,f1,f2,…,fk>，其子代数一定存在.第十一页，共77页。1112第十章群与环主要内容群的定义(dìngyì)与性质子群与群的陪集分解循环群与置换群环与域第十二页，共77页。1213根本(gēnběn)要求判断或证明给定集合和运算是否构成半群、独异点和群熟悉群的根本性质能够证明G的子集构成G的子群熟悉陪集的定义和性质熟悉拉格朗日定理及其推论，学习简单应用会求循环群的生成元及其子群熟悉n元置换的表示(biǎoshì)方法、乘法以及n元置换群能判断给定代数系统是否为环和域

第十三页，共77页。1314半群、独异点与群的定义(dìngyì)半群、独异点、群的实例群中的术语群的根本性质10.1群的定义(dìngyì)与性质第十四页，共77页。1415半群、独异点与群的定义(dìngyì)(1)设V=<S,∘>是代数系统(xìtǒng)，∘为二元运算，如果∘运算是可结合的，那么称V为半群.(2)设V=<S,∘>是半群，假设e∈S是关于∘运算的单位元，那么称V是含幺半群，也叫做独异点.有时也将独异点V记作V=<S,∘,e>.(3)设V=<S,∘>是独异点，eS关于∘运算的单位元，假设aS，a1S，那么称V是群.通常将群记作G.第十五页，共77页。1516有关(yǒuguān)群的术语(1)假设(jiǎshè)群G是有穷集，那么称G是有限群，否那么称为无限群.群G的基数称为群G的阶，有限群G的阶记作|G|.(2)只含单位元的群称为平凡群.

(3)假设(jiǎshè)群G中的二元运算是可交换的，那么称G为交换群或阿贝尔(Abel)群.定义10.4设G是群，a∈G，使得(shǐde)等式ak=e成立的最小正整数k称为a的阶，记作|a|=k，称a为k阶元.假设不存在这样的正整数k，那么称a为无限阶元.第十六页，共77页。1617群的性质(xìngzhì)：幂运算规那么设G为群，那么G中的幂运算(yùnsuàn)满足：(1)a∈G，(a1)1=a(2)a,b∈G，(ab)1=b1a1(3)a∈G，anam=an+m，n,m∈Z(4)a∈G，(an)m=anm，n,m∈Z(5)假设G为交换群，那么(ab)n=anbn.第十七页，共77页。1718群的性质(xìngzhì)：消去律；元素的阶G为群，那么(nàme)G中适合消去律，即对任意a,b,c∈G有(1)假设ab=ac，那么(nàme)b=c.(2)假设ba=ca，那么(nàme)b=c.例5设G是群，a,b∈G是有限(yǒuxiàn)阶元.证明(1)|b1ab|=|a|(2)|ab|=|ba|定理G为群，a∈G且|a|=r.设k是整数，那么(1)ak=e当且仅当r|k(2)|a1|=|a|第十八页，共77页。1819子群(zǐqún)与群的陪集分解设G是群，H是G的非空子集，(1)如果H关于(guānyú)G中的运算构成群，那么称H是G的子群,记作H≤G.(2)假设H是G的子群，且HG，那么称H是G的真子群，记作H<G.例如nZ(n是自然数)是整数加群<Z,+>的子群.当n≠1时,nZ是Z的真子群.

对任何群G都存在(cúnzài)子群.G和{e}都是G的子群，称为G的平凡子群.

第十九页，共77页。1920子群判定(pàndìng)定理〔判定定理一〕设G为群，H是G的非空子(kòngzi)集，那么H是G的子群当且仅当(1)a,b∈H有ab∈H(2)a∈H有a1∈H.定理〔判定(pàndìng)定理二〕设G为群，H是G的非空子集.H是G的子群当且仅当a,b∈H有ab1∈H.

定理〔判定定理三〕设G为群，H是G的非空有穷子集，那么H是G的子群当且仅当a,b∈H有ab∈H.第二十页，共77页。2021典型(diǎnxíng)子群的实例设G为群，a∈G，令H={ak|k∈Z}，那么(nàme)H是G的子群，称为由a生成的子群，记作<a>.定义(dìngyì)设G为群,令C={a|a∈G∧x∈G(ax=xa)}，那么C是G的子群，称为G的中心.例6

设G是群，H,K是G的子群.证明(1)H∩K也是G的子群(2)H∪K是G的子群当且仅当HK或KH第二十一页，共77页。2122陪集设H是G的子群(zǐqún)，a∈G.令

Ha={ha|h∈H}称Ha是子群(zǐqún)H在G中的右陪集.称a为Ha的代表元素.

定理设H是群G的子群(zǐqún)，那么(1)He=H(2)a∈G有a∈Ha定理(dìnglǐ)设H是群G的子群，那么a,b∈G有

a∈Hbab1∈HHa=Hb第二十二页，共77页。2223推论(tuīlùn)推论(tuīlùn)设H是群G的子群,那么(1)a,b∈G，Ha=Hb或Ha∩Hb=(2)∪{Ha|a∈G}=G证明：由等价类性质可得.定理设H是群G的子群，在G上定义(dìngyì)二元关系R：a,b∈G,<a,b>∈Rab1∈H那么R是G上的等价关系，且[a]R=Ha.第二十三页，共77页。2324左陪集的定义(dìngyì)与性质设G是群，H是G的子群，H的左陪集，即

aH={ah|h∈H}，a∈G关于左陪集有下述性质(xìngzhì)：(1)eH=H(2)a∈G，a∈aH(3)a,b∈G，a∈bHb1a∈HaH=bH(4)假设在G上定义二元关系R，

a,b∈G，<a,b>∈Rb1a∈H那么R是G上的等价关系，且[a]R=aH.(5)a∈G，H≈aH第二十四页，共77页。2425Lagrange定理(dìnglǐ)〔Lagrange〕设G是有限群，H是G的子群，那么|G|=|H|·[G:H]其中(qízhōng)[G:H]是H在G中的不同右陪集(或左陪集)数，称为H在G中的指数.推论1设G是n阶群，那么a∈G，|a|是n的因子，且有an=e.推论2对阶为素数的群G，必存在(cúnzài)a∈G使得G=<a>.

第二十五页，共77页。2526Lagrange定理(dìnglǐ)的应用命题：如果(rúguǒ)群G只含1阶和2阶元，那么G是Abel群.例8证明(zhèngmíng)6阶群中必含有3阶元.证设a为G中任意元素，有a1=a.任取x,y∈G，那么xy=(xy)1=y1x1=yx，因此G是Abel群.证设G是6阶群，那么G中元素只能是1阶、2阶、3阶或6阶.假设G中含有6阶元，设为a，那么a2是3阶元.假设G中不含6阶元，下面证明G中必含有3阶元.如假设不然，G中只含1阶和2阶元，即a∈G，有a2=e，由命题知G是Abel群.取G中2阶元a和b，ab，令H={e,a,b,ab}，那么H是G的子群，但|H|=4，|G|=6，与拉格朗日定理矛盾.

第二十六页，共77页。2627循环群与置换群设G是群，假设存在(cúnzài)a∈G使得G={ak|k∈Z}那么称G是循环群，记作G=<a>，称a为G的生成元.

循环群的分类：n阶循环群和无限循环群.

设G=<a>是循环群，假设(jiǎshè)a是n阶元，那么

G={a0=e,a1,a2,…,an1}那么|G|=n，称G为n阶循环群.假设(jiǎshè)a是无限阶元，那么

G={a0=e,a±1,a±2,…}称G为无限循环群.

第二十七页，共77页。2728循环群的生成元设G=<a>是循环群.

(1)假设(jiǎshè)G是无限循环群，那么G只有两个生成元，即a和a1.

(2)假设(jiǎshè)G是n阶循环群，那么G含有(n)个生成元.对于任何小于n且与n互质的数r∈{0,1,…,n-1},ar是G的生成元.(n)成为欧拉函数，例如n=12，小于或等于12且与12互素的正整数有4个：1,5,7,11，所以(12)=4.

第二十八页，共77页。2829循环群的子群(zǐqún)设G=<a>是循环群.

(1)设G=<a>是循环群，那么G的子群仍是循环群.(2)假设G=<a>是无限循环群，那么G的子群除{e}以外(yǐwài)都是无限循环群.(3)假设G=<a>是n阶循环群，那么对n的每个正因子d，G恰好含有一个d阶子群.

第二十九页，共77页。293010.4环与域

设<R,+,·>是代数系统，+和·是二元运算.如果满足以下条件:(1)<R,+>构成交换群(2)<R,·>构成半群(3)·运算关于+运算适合分配律那么称<R,+,·>是一个环.通常称+运算为环中的加法，·运算为环中的乘法(chéngfǎ).环中加法单位元记作0，乘法(chéngfǎ)单位元〔如果存在〕记作1.对任何元素x，称x的加法逆元为负元，记作x.假设x存在乘法(chéngfǎ)逆元的话，那么称之为逆元，记作x1.第三十页，共77页。3031定理(dìnglǐ)设<R,+,·>是环，那么

(1)a∈R，a0=0a=0

(2)a,b∈R，(a)b=a(b)=ab

(3)a,b,c∈R，a(bc)=abac，(bc)a=baca

(4)a1,a2,...,an,b1,b2,...,bm∈R(n,m≥2)

环的运算(yùnsuàn)性质第三十一页，共77页。3132特殊(tèshū)的环设<R,+,·>是环(1)假设环中乘法·适合交换律，那么称R是交换环(2)假设环中乘法·存在单位(dānwèi)元，那么称R是含幺环(3)假设a,b∈R，ab=0a=0∨b=0，那么称R是无零因子环(4)假设R既是交换环、含幺环、无零因子环，那么称R是整环(5)设R是整环，且R中至少含有两个元素.假设a∈R*，其中R*=R{0}，都有a－1∈R，那么称R是域.第三十二页，共77页。3233第五(dìwǔ)局部图论本局部主要(zhǔyào)内容图的根本概念欧拉图、哈密顿图树平面图支配集、覆盖集、独立集、匹配与着色第三十三页，共77页。3334第十四章图的根本(gēnběn)概念主要内容图通路与回路图的连通性图的矩阵表示图的运算预备知识多重集合(jíhé)——元素可以重复出现的集合(jíhé)无序集——AB={(x,y)|xAyB}第三十四页，共77页。3435根本(gēnběn)要求深刻理解握手定理及推论的内容并能灵活地应用它们深刻理解图同构、简单图、完全图、正那么图、子图、补图、二部图的概念以及它们的性质及相互之间的关系记住通路与回路的定义、分类及表示法深刻理解与无向图连通性、连通度有关的诸多概念会判别有向图连通性的类型(lèixíng)熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法，会求可达矩阵第三十五页，共77页。3536相关(xiāngguān)概念1.图①可用G泛指图〔无向的或有向的〕②V(G),E(G),V(D),E(D)③n阶图2.有限(yǒuxiàn)图3.n阶零图与平凡图〔1阶零图〕4.空图——5.用ek表示无向边或有向边6.顶点与边的关联关系①关联、关联次数②环③孤立点7.顶点之间的相邻与邻接关系第三十六页，共77页。3637多重图与简单(jiǎndān)图定义14.3(1)无向图中的平行边〔大于1条〕及重数(2)有向图中的平行边及重数〔注意(zhùyì)方向性〕(3)多重图〔含平行边的图〕(4)简单图〔既不含边，也不含环的图〕在定义14.3中定义的简单图是极其重要的概念第三十七页，共77页。3738顶点(dǐngdiǎn)的度数(1)设G=<V,E>为无向图,vV,d(v)——v的度数(dùshu),简称度(2)设D=<V,E>为有向图,vV,d+(v)——v的出度d(v)——v的入度d(v)——v的度或度数(dùshu)(3)(G),(G)(4)+(D),+(D),(D),(D),(D),(D)(5)奇顶点度与偶度顶点第三十八页，共77页。3839定理设G=<V,E>为任意(rènyì)无向图，V={v1,v2,…,vn},|E|=m,那么

推论任何图(无向(wúxiànɡ)或有向)中，奇度顶点的个数是偶数.握手(wòshǒu)定理定理设D=<V,E>为任意有向图，V={v1,v2,…,vn},|E|=m,那么第三十九页，共77页。3940图的度数列(shùliè)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)都不是(bùshi)可简单图化的，特别是后者也不是(bùshi)可图化的第四十页，共77页。4041n阶完全(wánquán)图与竞赛图定义14.6(1)n(n1)阶无向完全图——每个顶点与其余顶点均相邻的无向简单图，记作Kn.简单性质：边数(2)n(n1)阶有向完全图——每对顶点之间均有两条方向(fāngxiàng)相反的有向边的有向简单图.简单性质：(3)n(n1)阶竞赛图——基图为Kn的有向简单图.简单性质：边数

第四十一页，共77页。4142子图G=<V,E>,G=<V,E>(1)GG——G为G的子图，G为G的母图(2)假设GG且V=V，那么(nàme)称G为G的生成子图(3)假设VV或EE，称G为G的真子图(4)V〔VV且V〕的导出子图，记作G[V](5)E〔EE且E〕的导出子图，记作G[E]第四十二页，共77页。4243补图设G=<V,E>为n阶无向简单图，以V为顶点集，以所有(suǒyǒu)使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作.假设G,那么称G是自补图.第四十三页，共77页。434414.2通路(tōnglù)与回路给定图G=<V,E>〔无向或有向的〕，G中顶点与边的交替序列(xùliè)=v0e1v1e2…elvl，vi1,vi是ei的端点.(1)通路与回路：为通路；假设v0=vl，为回路，l为回路长度.(2)简单通路与回路：所有边各异，为简单通路，又假设v0=vl，为简单回路(3)初级通路(路径)与初级回路(圈)：中所有顶点各异，那么称为初级通路(路径)，又假设除v0=vl，所有的顶点各不相同且所有的边各异，那么称为初级回路(圈)(4)复杂通路与回路：有边重复出现第四十四页，共77页。4445通路(tōnglù)与回路的长度在n阶图G中，假设从顶点(dǐngdiǎn)vi到vj〔vivj〕存在通路，那么从vi到vj存在长度小于或等于n1的通路.推论在n阶图G中，假设从顶点(dǐngdiǎn)vi到vj〔vivj〕存在通路，那么从vi到vj存在长度小于或等于n1的初级通路〔路径〕.在一个n阶图G中，假设存在vi到自身的回路，那么一定存在vi到自身长度小于或等于n的回路.推论在一个n阶图G中，假设存在vi到自身的简单回路，那么一定存在长度小于或等于n的初级回路.第四十五页，共77页。4546图的连通性无向图的连通性(1)顶点之间的连通关系：G=<V,E>为无向图①假设vi与vj之间有通路(tōnglù)，那么vivj②是V上的等价关系R={<u,v>|u,vV且uv}(2)G的连通性与连通分支①假设u,vV，uv，那么称G连通②V/R={V1,V2,…,Vk}，称G[V1],G[V2],…,G[Vk]为连通分支，其个数p(G)=k(k1)；k=1，G连通第四十六页，共77页。4647无向(wúxiànɡ)图的连通度1.删除顶点及删除边Gv——从G中将v及关联的边去掉(qùdiào)GV——从G中删除V中所有的顶点Ge——将e从G中去掉(qùdiào)GE——删除E中所有边2.点割集与边割集点割集与割点G=<V,E>,VVV为点割集——p(GV)>p(G)且有极小性v为割点——{v}为点割集G=<V,E>,EEE是边割集——p(GE)>p(G)且有极小性e是割边〔桥〕——{e}为边割集第四十七页，共77页。4748有向图的连通性D=<V,E>为有向图vivj〔vi可达vj〕——vi到vj有通路vivj〔vi与vj相互可达〕性质具有自反性(vivi)、传递性具有自反性、对称性、传递性vi到vj的短程(duǎnchénɡ)线与距离类似于无向图中，只需注意距离表示法的不同(无向图中d(vi,vj)，有向图中d<vi,vj>)及d<vi,vj>无对称性第四十八页，共77页。4849有向图的连通性及分类(fēnlèi)D=<V,E>为有向图D弱连通(连通)——基图为无向连通图D单向连通——vi,vjV，vivj或vjviD强连通——vi,vjV，vivj易知，强连通单向连通弱连通判别法D强连通当且仅当D中存在经过每个顶点至少(zhìshǎo)一次的回路D单向连通当且仅当D中存在经过每个顶点至少(zhìshǎo)一次的通路第四十九页，共77页。4950二部图设G=<V,E>为一个无向图，假设能将V分成V1和V2(V1V2=V，V1V2=)，使得G中的每条边的两个端点都是一个属于V1，另一个属于V2，那么称G为二部图(或称二分(èrfēn)图、偶图等)，称V1和V2为互补顶点子集，常将二部图G记为<V1,V2,E>.又假设G是简单二部图，V1中每个顶点均与V2中所有的顶点相邻，那么称G为完全二部图，记为Kr,s，其中r=|V1|，s=|V2|.注意，n阶零图为二部图.第五十页，共77页。5051有向图的邻接矩阵〔无限制(xiànzhì)〕设有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令为顶点vi邻接到顶点vj边的条数，称为(chēnɡwéi)D的邻接矩阵，记作A(D)，或简记为A.性质

第五十一页，共77页。5152推论设Bl=A+A2+…+Al〔l1〕，那么(nàme)Bl中元素为D中长度为l的通路(tōnglù)总数，定理设A为有向图D的邻接矩阵，V={v1,v2,…,vn}为顶点集，那么(nàme)A的l次幂Al〔l1〕中元素为D中vi到vj长度为

l的通路数，其中为vi到自身长度为l的回路数，而为D中长度小于或等于l的回路数为D中长度小于或等于l的通路数.邻接矩阵的应用为D中长度为l的回路总数.

第五十二页，共77页。5253定义(dìngyì)设D=<V,E>为有向图.V={v1,v2,…,vn},令有向图的可达矩阵(jǔzhèn)〔无限制〕称(pij)nn为D的可达矩阵，记作P(D)，简记为P.由于viV，vivi，所以P(D)主对角线上的元素(yuánsù)全为1.由定义不难看出,D强连通当且仅当P(D)为全1矩阵.以下图所示有向图D的可达矩阵为第五十三页，共77页。5354第十五章欧拉图与哈密顿图主要内容(nèiróng)欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图带权图、货郎担问题第五十四页，共77页。5455根本(gēnběn)要求根本要求深刻理解欧拉图、半欧拉图的定义及判别定理深刻理解哈密顿图、半哈密顿图的定义.会用哈密顿图的必要条件判断某些图不是(bùshi)哈密顿图.会用充分条件判断某些图是哈密顿图.要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要条件.第五十五页，共77页。5556欧拉图定义(dìngyì)定义15.1(1)欧拉通路——经过图中每条边一次且仅一次行遍所有顶点的通路.(2)欧拉回路——经过图中每条边一次且仅一次行遍所有顶点的回路.(3)欧拉图——具有欧拉回路的图.(4)半欧拉图——具有欧拉通路而无欧拉回路的图.几点说明(shuōmíng)：规定平凡图为欧拉图.欧拉通路是生成的简单通路，欧拉回路是生成的简单回路.环不影响图的欧拉性.第五十六页，共77页。5657无向(wúxiànɡ)欧拉图的判别法无向图G是欧拉图当且仅当G连通(liántōng)且无奇度数顶点.无向图G是半欧拉图当且仅当G连通(liántōng)且恰有两个奇度顶点.第五十七页，共77页。5758有向欧拉图的判别(pànbié)法有向图D是欧拉图当且仅当D是强连通(liántōng)的且每个顶点的入度都等于出度.有向图D是半欧拉图当且仅当D是单向连通(liántōng)的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度.G是非平凡的欧拉图当且仅当G是连通(liántōng)的且为假设干个边不重的圈之并.第五十八页，共77页。5859哈密顿图与半哈密顿图

(1)哈密顿通路——经过图中所有顶点一次仅一次的通路.(2)哈密顿回路——经过图中所有顶点一次仅一次的回路.(3)哈密顿图——具有(jùyǒu)哈密顿回路的图.(4)半哈密顿图——具有(jùyǒu)哈密顿通路且无哈密顿回路的图.几点说明：平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路.环与平行边不影响哈密顿性.哈密顿图的实质是能将图中的所有顶点排在同一个圈上第五十九页，共77页。5960无向哈密顿图的一个(yīɡè)必要条件设无向图G=<V,E>是哈密顿图，对于(duìyú)任意V1V且V1，均有p(GV1)|V1|推论(tuīlùn)设无向图G=<V,E>是半哈密顿图，对于任意的V1V且V1均有p(GV1)|V1|+1第六十页，共77页。6061无向(wúxiànɡ)哈密顿图的一个充分条件设G是n阶无向简单图，假设对于任意(rènyì)不相邻的顶点vi,vj，均有d(vi)+d(vj)n1()那么G中存在哈密顿通路.推论设G为n(n3)阶无向简单图，假设对于G中任意(rènyì)两个不相邻的顶点vi,vj，均有d(vi)+d(vj)n〔〕那么G中存在哈密顿回路，从而G为哈密顿图.第六十一页，共77页。6162第十六章

树主要内容无向树及其性质生成树、最小生成树、根本回路(huílù)系统、根本割集系统根树及其分类、最优树、最正确前缀码、波兰符号法、逆波兰符号法第六十二页，共77页。6263根本(gēnběn)要求根本要求深刻理解无向树的定义及性质熟练地求解无向树准确地求出给定带权连通图的最小生成树深刻理解根本回路、根本割集的概念，并会计算理解根树及其分类等概念会画n阶〔n较小〕非同构的无向树及根树〔1n6〕熟练掌握(zhǎngwò)求最优树及最正确前缀码的方法掌握(zhǎngwò)波兰符号法与逆波兰符号法第六十三页，共77页。636416.1无向树及其性质(xìngzhì)

(1)无向树——连通无回路的无向图(2)平凡树——平凡图(3)森林(sēnlín)——至少由两个连通分支〔每个都是树〕组成(4)树叶——1度顶点(5)分支点——度数2的顶点

第六十四页，共77页。6465无向(wúxiànɡ)树的等价定义设G=<V,E>是n阶m条边的无向图，那么下面各命题是等价的：(1)G是树(2)G中任意两个顶点之间存在(cúnzài)惟一的路径.(3)G中无回路且m=n1.(4)G是连通的且m=n1.(5)G是连通的且G中任何边均为桥.(6)G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的圈.定理设T是n阶非平凡的无向树，那么(nàme)T中至少有两片树叶.第六十五页，共77页。6566不一定连通，也不一定不含回路，如图所示定义16.2

设G为无向图(1)G的树——T是G的子图并且是树(2)G的生成树——T是G的生成子图并且是树(3)生成树T的树枝——T中的边(4)生成树T的弦——不在T中的边(5)生成树T的余树——全体弦组成的集合的导出子图16.2生成(shēnɡchénɡ)树第六十六页，共77页。6667推论2

的边数为mn+1.推论3

为G的生成树T的余树，C为G中任意一个圈，则C与一定有公共边.证否则，C中的边全在T中，这与T为树矛盾.定理无向图G具有生成(shēnɡchénɡ)树当且仅当G连通.生成(shēnɡchénɡ)树存在条件推论1G为n阶m条边的无向连通(liántōng)图，那么mn1.证必要性显然.充分性用破圈法〔注意：在圈上删除任何一条边，不破坏连通性〕第六十七页，共77页。6768根本回路(huílù)系统设T为G的生成(shēnɡchénɡ)树，e为T的任意一条弦，那么Te中含一个只有一条弦其余边均为T的树枝的圈.不同的弦对应的圈也不同.定义设T是n阶m条边的无向连通图G的一棵生成树，设e1,e2,…,emn+1为T的弦.设Cr为T添加弦er产生的只含弦er、其余边均为树枝的圈.称Cr为G的对应树T的弦er的根本(gēnběn)回路或根本(gēnběn)圈，r=1,2,…,mn+1.并称{C1,C2,…,Cmn+1}为G对应T的根本(gēnběn)回路系统，称mn+1为G的圈秩，记作(G).第六十八页，共77页。6869根本(gēnběn)割集的存在设T是连通图G的一棵生成树，e为T的树枝(shùzhī)，那么G中存在只含树枝(shùzhī)e，其余边都是弦的割集，且不同的树枝(shùzhī)对应的割集也不同.定义设T是n阶连通图G的一棵生成(shēnɡchénɡ)树，e1,e2,…,en1为T的树枝，Si是G的只含树枝ei的割集，那么称Si为G的对应于生成(shēnɡchénɡ)树T由树枝ei生成(shēnɡchénɡ)的根本割集，i=1,2,…,n1.并称{S1,S2,…,Sn1}为G对应T的根本割集系统，称n1为G的割集秩，记作(G).第六十九页，共77页。6970最小生成(shēnɡchénɡ)树T是G=<V,E,W>的生成(shēnɡchénɡ)树(1)W(T)——T各边权之和(2)最小生成(shēnɡchénɡ)树——G的所有生成(shēnɡchénɡ)树中权最小的求最小生成树的一个算法避圈法〔Kruskal〕设G=<V,E,W>，将G中非环边按权从小到大排序：e1,e2,…,em.(1)取e1在T中(2)查e2，假设(jiǎshè)e2与e1不构成回路，取e2也在T中，否那么弃e2.(3)再查e3,…,直到得到生成树为止.第七十页，共77页。707116.3根树及其应用(yìngyòng)T是有向树〔基图为无向树〕(1)T