离散数学习题评讲3.ppt

代数系统/图论部分习题讲评 习题53 （2）设S,*是一个半群，aS,在S上定义一个二元运算，使得对于S中的任意元素x和y,都有xy=x*a*y,证明二元运算是可结合的。 证明：S中任取元素x,y,z,则 x(yz)=x(y*a*z)=x*a*(y*a*z) =(x*a*y)*a*z =(xy)*a*z=(xy)z 习题54 (5)设是群，且A2n,nI+。证明：在A中至少存在ae,使得a*a=e。其中e为幺元。,证明：a*a=e即表明存在元素ae以自身为逆元，除去幺元e之外，余下任一元素都不以自身为逆元，则余下的元素数目必须为偶数才能互相配对，因为|A|=2n,除去幺元外，还有2n-1个元素，不可能互相配对，故其中至少有一个元素必须以自身为逆元。 习题5-5 (1)设是一个独异点，并且对于G中的每一个元素x都有x*x=e,其中e是幺元，证明是一个阿贝尔群。 证明：G中任取元素x,y,令x*y=a,y*x=b,则 a*b=(x*y)*(y*x)=e,两边左*a, a*(a*b)=a*e,得b=a,故x*y=y*x,为阿贝尔群。,习题5-7 (7) 设aH和bH是H在G中的两个左陪集，证明：要么aHbH=,要么aH=bH。 证明：根据拉格郎日定理，H的所有左陪集形成等价类并决定了一个等价关系R，因此，当且仅当aRb时，aH=bH,aRb时，a，b分属不同的等价类，有aHbH= ，故要么aHbH=,要么aH=bH。 (8)设p是质数，证明：pm阶群中一定包含着一个p阶子群。,证明：由拉格朗日定理及其推论可知，pm阶群中除幺元外其余元素的阶次只能为p,p2,pm, 设某元素a的阶次为pk(1到的同态映射，g是由到的同态映射，那么gf是到的同态映射。,证明：任取a,bA,则 g f(ab)=g(f(a)*f(b)=g(f(a) g(f(b) =g f(a) g f(b)，故g f是g f是到的同态映射。 (6)证明：循环群的同态象必定是循环群。 证明：设f是循环群到代数系统是同态映射，若的生成元为a,设f(a)=r，设f(ak)=rk,kI+且k0,则 f(ak+1)=f(ak)f(a)= rkr= rk+1,故 f(ak)= rk,kI+且k0成立。 同态象f(A)中任取元素b，则存在xA,使得f(x)=b,设x=am,有b=rm,即f(A)中任一元素b都可由r生成。,习题7-1 （1）证明在任何有向完全图中，所有结点入度的平方之和等于所有结点的出度平方之和。 证明：设有向完全图中有n个顶点，顶点记为 v1,v2,vn,设第k个（k=1,2,n）顶点vk的出度为xk,入度为yk,因为有向完全图，故有xk+yk=n,习题7-5 （2）证明：小于30条边的平面简单图有一个结点度数小于等于4。 证明：假设该平面简单图中没有结点度数小于等于4，则所有结点度数大于等于5，设顶点数为v,边数为e,面数为r,有 2e5v ，即v(2/5)e 又每面次数不低于3，有2e3r, 即r(2/3)e 根据欧拉