《离散数学习题评讲3》由会员分享，可在线阅读，更多相关《离散数学习题评讲3（7页珍藏版）》请在金锄头文库上搜索。
1、代数系统/图论部分习题讲评 习题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个元
2、素 ，不可能互相配对，故其中至少有一个元素必须 以自身为逆元。 习题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分属不同的等 价类，有a
3、HbH= ，故要么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
4、+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根据欧拉公式 v+r-e=2,得(2/5)e+(2/3)e-e2,得e30，与e小于30矛盾 ，故假设不成立，一定存在顶点度数小于等于4 。
