离散二总复习.

离散二总复习代数系统熟练掌握二元运算性质的判断及证明。掌握代数系统的同构定义和证明，了解同构性质的保持。熟练掌握半群,独异点和群的概念。熟悉群的阶、群中元素的阶以及群的基本性质。掌握子群的证明。熟悉陪集的定义和性质。熟悉Lagrange定理及其推论,学会简单应用。代数系统掌握循环群和循环周期的概念。掌握有限循环群生成元及其子群的求法。掌握环与域的概念。群中的简单证明主要包括：群中的等式（元素相等或集合相等）与元素的阶相关的命题群的其它简单命题，如交换性等经常使用的工具：算律：结合律、消去律和特殊元素相关的等式，如单位元、逆元等。幂运算规则和元素的阶相关的性质。（如：a为2阶元的充分必要条件是a-1=a等）基本运算和性质练习1：给定群G,*，*的运算表如右图所示。求解下面群的方程：b*d-1*x*c=d*c-1解:b*d-1*x*c=d*c-1∵d-1=bc-1=c∴b*b*x*c=d*c∵b*b=c∴c*x*c=d*c消去c得c*x=d解得:x=c-1*d=c*d=b*abcdaabcdbbcdaccdabddabc群中的简单证明习题2：给定集合G＝{x|x是有理数且x≠1}，在G上定义二元运算*如下：任何a,b∈Ga*b=a+b-ab求证G,*是个交换群。证明：封闭、结合、含幺、可逆、交换群中的简单证明习题3：设G为群，任取x∈G，有x2=e,证明G是交换群。证明：∵x2=e∴x-1=x可证明在群G中111()()xyxyyxyx群中的简单证明习题4：偶数阶群中必含2阶元。证明：如果元素x的阶大于2，则x-1≠x，x与它的逆元成对出现，由于群中元素个数为偶数个，则除幺元e外，一定有2阶元。子群的证明习题5：设G为群，a是G中的2阶元，证明G中与a可交换的元素构成G的子群。证明：令H={x|x∈G∧xa=ax},下面证明H是G的子群。首先e属于H，H是G的非空子集。任取x,y∈H，有(xy-1)a=x(y-1a)=x(a-1y)-1=x(ay)-1=x(ya)-1=xa-1y-1=xay-1=axy-1=a(xy-1)因此xy-1属于H。由判定定理命题得证。子群的证明习题6：设f和g都是群G1,到G2,的同态，证明C,是G1,的一个子群，其中C={x|x∈G1且f(x)=g(x)}证明：用子群定义证明C,满足：a)封闭性。任取a,b∈C，∴f(a)=g(a)f(b)=g(b)f(ab)=f(a)f(b)=g(a)g(b)=g(ab)∴ab∈Cb)证幺元e1∈C,设e1和e2分别是G1和G2中的幺元,因f(e1)=e2=g(e1)∴e1∈C。c)可逆性：任取x∈C,f(a)=g(a)a-1∈G1,f(a-1)=(f(a))-1=(g(a))-1=g(a-1)∴a-1∈C。综上所述，C,是G1,的一个子群。拉格朗日定理应用实例习题7：证明6阶群G中必含有3阶元。应用习题3结论：只含有1阶和2阶元的群是Abel群。证明：由拉格朗日定理推论可知G中只能含有1,2,3,6阶元。若含有6阶元，则一定含有3阶元。若不含6阶元，则G中含有1个幺元和5个2阶元，且为交换群。若只有二阶元x,y∈G，则xy=yx∈G，G中只有4个元素；若另有z∈G，则xz≠yz∈G，G中有7个元素，所以如果不含有3阶元，G中的元素个数一定不为6。矛盾。习题8：设H1,H2分别是群G的r,s阶子群，若r,s互素，证明H1∩H2={e}。拉格朗日定理应用实例证明：H1H2是H1和H2的子群。由Lagrange定理，|H1H2|整除r，也整除s。从而|H1H2|整除r与s的最大公因子。因为(r,s)=1，从而|H1H2|=1。即H1H2={e}。群的同态与同构习题9：定义群G上的函数f，f(x)=x-1，x∈G，证明f为自同构当且仅当G为交换群。证明：必要性：任取x,y∈G,xy=f((xy)-1)=f(y-1x-1)=f(y-1)f(x-1)=yx充分性：易见f为双射。任取x,y∈G,有f(xy)=f(yx)=(yx)-1=x-1y-1=f(x)f(y)循环群习题10：设群G的运算表如表所示，问G是否为循环群？如果是，求出它所有的生成元和子群。abcdefbcdefacdefabdefabcefabcdfabcdeabcdefabcdefabcdefbcdefacdefabdefabcefabcdfabcdeabcdefabcdef解：易见a为单位元。由于|G|=6,|b|=6,所以b为生成元.G=b为循环群.|f|=6,因而f也是生成元|c|=3,|d|=2,|e|=3,因此c,d,e不是生成元。子群：a={a},c={c,e,a},d={d,a},G。环与域习题11：在整数环中定义∗和◇两个运算,a,b∈Z有a∗b=a+b1,a◇b=a+bab.证明Z,∗,◇构成环证明a,b∈Z有a∗b,a◇b∈Z,两个运算封闭。任取a,b,c∈Z，证明∗与◇可结合，1为∗的单位元。2a为a关于∗的逆元。Z关于∗构成交换群,关于◇构成半群。◇关于∗满足分配律。a◇(b∗c)=a◇(b+c1)=2a+b+cabac1a◇b)∗(a◇c)=2a+b+cabac1Z,∗,◇构成环环与域习题12：判断下列集合和给定运算是否构成环、整环和域,如果不构成,说明理由.(1)A={a+bi|a,b∈Q},其中i2=1,运算为复数加法和乘法(2)A={2z+1|z∈Z},运算为实数加法和乘法(3)A={2z|z∈Z},运算为实数加法和乘法(4)A={x|x≥0∧x∈Z},运算为实数加法和乘法(5)}Q,|5{4babaA,运算为实数加法和乘法课后习题5-1:(1)(2)5-2:(1)(2)(5)5-3:(3)(5)5-4:(1)(2)(5)5-5:(2)(4)5-7:(3)(5)5-8:(2)(3)(11)第九章：2、4、5、6、8、11、15、17、18第十章：2、8、9、20、34格与布尔代数掌握格的定义，了解格的性质及格同态。能够证明格中的等式和不等式。能判别格L的子集S是否构成子格。能够判断格，分配格，有补格和布尔格。掌握布尔代数中的运算性质。1、格的定义与性质偏序集构成格的条件：任意二元子集都有最大下界和最小上界。格的实例：正整数的因子格，幂集格，子群格。格的性质：对偶原理，格中运算律（交换、结合、幂等、吸收），保序性，分配不等式。格作为代数系统的定义。习题1.判断下述偏序集是否构成格？如果不是说明理由。2.求下述命题的对偶命题。（1）(a∧b)∨b=b（2）b∨(c∧a)≤(b∨c)∧a习题3.证明题（1）(a∧b)∨b=b（2）(a∧b)∨(c∧d)≤(a∨c)∧(b∨d)2、子格与格同态子格判定定理。格L的非空子集S构成L的子格的条件：S对L的两个运算封闭。函数f构成格同态的条件：f(a∧b)=f(a)∧f(b),f(a∨b)=f(a)∨f(b)习题1.求格L的所有子格。2.任取格L的元素a，令S={x|x∈L且x≤a}，证明S是L的子格。dabec3、分配格与有补格如果格中一个运算对另一个运算是可分配的，称这个格是分配格。分配格的两种判别法：不存在与钻石格或五角格同构的子格；对于任意元素a,b,c，有a∧b=a∧c且a∨b=a∨cb=c有界格的定义及其实例。格中元素的补元及其性质（分配格中补元的唯一性）有补格的定义习题1.判别下面L是否为分配格。2.求出每个格的所有的补元，说明它们是否为有补格。fbdaehcfbaegccfaebdgdL1L2L3习题3、给出有界格如图，回答以下问题：a)哪些元素有补元？指出其补元。b)该格是分配格吗？为什么？c)该格是有补格吗？为什么？1cabdfge01cabdfge0答案：a)a、c、d、f、g无补元;b和e互为补元;0和1互为补元.b)不是分配格,因为它含有五元素非分配环格。c)它不是有补格,因为很多元素无补元。4、布尔代数会判别一个格是布尔格。证明布尔代数中的等式。了解任意有限布尔代数都与某个幂集格同构。习题1.设B,∧,∨,-,0,1是布尔代数，证明对于B中任意元素a,bbababa10)2(babaa)()1(习题2.判断下述代数系统是否为格？是不是布尔代数？（1）S={1,3,4,12}，x,y∈S，xy与xy分别表示x与y的最小公倍数和最大公约数。（2）S={0,1,2}，为模3加法，为模2乘法（3）S={0,...,n},其中n≥2;任给x,y∈S,xy=max(x,y),xy=min(x,y)。课后习题小本6-1（1）（2）（4）6-2（2）（5）6-3（1）（3）（4）（6）6-4（2）（6）（8）大本习题十一4、6、8、12图的基本概念无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图；握手定理与推论；图的同构通路与回路及其分类无向图的连通性与连通度有向图的连通性及其分类图的矩阵表示及基本含义习题1、9阶无向图G中，每个顶点的度数不是5就是6。证明G中至少有5个6度顶点或至少有6个5度顶点。证明：关键是利用握手定理的推论。方法一：穷举法设G中有x个5度顶点，则必有(9x)个6度顶点，由握手定理推论可知，(x,9x)只有5种可能：(0,9),(2,7),(4,5),(6,3),(8,1）它们都满足要求。方法二：反证法否则，由握手定理推论可知，“G至多有4个5度顶点并且至多有4个6度顶点”，这与G是9阶图矛盾。习题2．数组2,2,2,2,3,3能简单图化吗？若能，画出尽可能多的非同构的图来。解答：只要能画出6阶无向简单图，就说明它可简单图化。下图的4个图都以此数列为度数列，请证明它们彼此不同构，都是K6的子图。习题3、有向图D如图所示，回答下列问题：(1)写出D的邻接矩阵。(2)D是哪类连通图?(3)D中v1到v4长度为1,2,3,4的通路各多少条？讨论它们的类型（简单通路还是初级通路）。(4)D中v1到v1长度为1,2,3,4的回路各多少条？讨论它们的类型（简单回路还是初级回路）。(5)D中长度为4的通路（不含回路）有多少条？(6)D中长度4的通路有多少条？其中有几条是回路？(7)写出D的可达性矩阵。课后习题第十四章:1、2、3、4、5、6、7、8、9、12、13、14、15、16、17、18、19、20、21、22、23、24、25、26、27、28、30、31、32、35、37、38、39、40、41、4445、46、47、49欧拉图和汉密尔顿图掌握欧拉图、半欧拉图的定义及判别定理掌握汉密顿图、半汉密顿图的定义能够用汉密顿图的必要条件和充分条件分别进行判断。要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要条件掌握欧拉图和汉密尔顿图的简单应用习题1.设G为n（n2）阶无向欧拉图，证明G中无桥证明：设C为G中一条欧拉回路，任意的eE(C)，可知Ce是Ge的子图，由()知Ce连通，所以e不为桥。习题2.某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都与两边的人交谈？解答：设计图并证明为H图习题3.距离(公里)如图所示。如何走行程最短？解答：最短的路为ABCDA，距离为36公里课后习题第十五章：1,2,8,9,11,12,13,14,15,16,20,21,22树掌握无向树的定义及性质熟练求解无向树准确求解给定带权连通图的最小生成树掌握基本回路、基本割集的概念，并会计算理解根树及其分类等概念熟练掌握求最优树及最佳前缀码的方法掌握二叉树的遍历习题1.请画出K5的所有不同构的生成树。解答：K5的生成树T边数为4,T的度数和为8有3棵（略）2.一棵正则二叉树有e条边，t个叶结点，