离散数学第二版答案6-7章.doc

第六章 代数系统6.1第129页1证明：任取，因此，二元运算*是可交换的；任取，因此，运算*是可结合的。该运算的么元是0，0的逆元是0，2的逆元是2，其余元素没有逆元。2证明：任取，由知，*运算不是可交换的。任取，由，知，*运算是可结合的。任取，可知N中的所有元素都是等幂的。*运算有右么元，任取，知N中的所有元素都是右么元。*运算没有左么元。证明：采用反证法。假定为*运算的左么元，取，由*的运算公式知，由么元的性质知，得，这与相矛盾，因此，*运算没有左么元。3解： 任取因此对于任意的都有，即二元运算*是可交换的。 任取因此对于任意的，都有，即二元运算*是可结合的。 设幺元为，则，即幺元为1. 对于所有的元素，都有，所以所有元素都是等幂的。4解：设 设是上的二元运算，则是一个从的映射。求上有多少个二元运算即相当于求这样的映射的个数。由于，映射的个数为，即上有个二元运算。 可交换即设集合，要求上可交换的二元运算的个数，即相当于求映射的个数，其中：具体如下图所示： 此时映射的个数推广到有个元素时，映射的个数 单位元素即幺元，若存在必唯一。设集合，若幺元为1，则有 此时的二元运算的个数相当于求映射的个数，其中： 映射的个数为幺元为2，3，4时同理，因此集合上有个有单位元素的二元运算。推广到有个元素时，具有单位元素的二元运算的个数为。5解：任取 对于任意的都有，故二元运算*是可交换的。若，此时故二元运算*是不可结合的。不存在这样使得任意的都有，因此，二元运算*不含幺元。对于任意的都有，故二元运算*是可交换的。故二元运算*是不可结合的。不存在这样使得任意的都有，因此，二元运算*不含幺元。 因此，二元运算*是不可交换的。故二元运算*是不可结合的。由于二元运算*不是可交换的，所以不存在这样使得任意的都有，因此，二元运算*不含幺元。6设是中的任意元素。由于二元运算*是可结合的，故又对于任意的，若，则故即对于中的任意元素，都有，所以中的 每一个元素都是等幂的。6.2第137页4证明：首先，U和V都只含有一个二元运算，因此是同类型的；第二，的定义域是自然数集合，值域是，是V定义域的子集。第三，验证是否运算的像等于像的运算。任取，分情况讨论：（1） x和y都可以表示成，设，那么，（2） x和y都不能表示成，那么也不能表示成,（3） x可以表示成，y不能表示成，那么也不能表示成,（4） x不可以表示成，y能表示成，那么也不能表示成,可知，无论x和y如何取值，都能够保证。综上所述，是U到V的同态映射。5证明：设，首先，U和V都仅有一个二元运算，因此U和V是同类型的；第二，U和V的定义域大小相同，具备构成双射函数的条件；第三，寻找特异元素，U中么元是a，右零元是c，三个元素都是等幂元；V中么元是3，右零元是1，三个元素都是等幂元。第四，在U和V的定义域之间构造双射函数，使得。把*运算表中的元素都用f下的像点代替，得321321321222111调整表头的顺序为1，2，3，转变为下表123123111222123跟V中运算表完全相同，因此代数系统和是同构的。6.证明：(1) 两个代数系统都只存在一个二元运算，故满足同型。(2) 构造函数，使得fX=X，显然是双射函数。(3) 对于任意的 fXY=XY=XY fXfY=XY故 fXY=fXfY，所以满足运算的像=像的运算。由(1),(2),(3)可知，两代数系统是同构的。7.解：当时，零同态；当时，恒等映射，自同态；当时，；当时，；当时，；当时，自同构。8.证明：的个复数根可表示成：(1) 与都含有一个二元运算，故为同型的。(2) 与定义域大小相同，具备构成双射函数的条件。(3) 构造双射函数对于任意的，因此，。由(1),(2),(3)可知，同构于。9证明：(1) 是代数系统到当的同态映射 又是的子代数(2) 对于，必存在，使得，由于为代数系统到当的同态映射，又是的子代数故对*运算封闭，即对运算满足封闭性。由(1),(2),(3)可知, 为的子代数。6.3第141页1解：解：首先，判断是否是等价关系。任取，由于，因此，是自反的；任取，若，即（），则，因此是对称的；任取，若，则（），（），于是，因此，可知是可传递的。因此，是等价关系。 其次，判断关于*是否满足代换性质。任取，若，即存在某个，满足则于是由于，因此，关于*是满足代换性质。综上所述，是上的同余关系。2.解：（1）对于+运算，在二元运算下，任取，验证下式是否成立取，可知满足，但，即。可知对于运算+，R不满足代换性质。（2）对于运算，在二元运算下，任取，若，则必然满足于是可得。由取值的任意性可知，对于运算，R满足代换性质。3证明：(1) 对于，有 由于对具有代换性质，所以有 由此可知：同理可知：因是等价关系，故是可传递的，所以有所以对具有代换性质。(2) 对具有代换性质，但对不具有代换性质，因4设代数系统，为同余关系。(1)即证：为同余关系证明：为等价关系若对任意 有, 则， ， ， ， 为同余关系所以为同余关系。 (2) 为等价关系若对任意 有, , 未必有， ， ， ， 因此，可能不满足代换性质所以未必是同余关系。5（1）解：R不是上的同余关系，取则，但是，因此，不满足代换性质。（2）, 当且仅当解：R不是上的同余关系，取，则，但，R不满足可传递性，不是等价关系。（3）解：R不是上的同余关系，取取则，但是，因此，不满足代换性质。（4）解：R不是上的同余关系，取，则，但，即，R不满足对称性，不是等价关系。6.4第143页1.解：（1）设其中，任取下面通过运算表构造*运算（这里仅给出了一个运算表，另一个照推）（2）设其中，任取运算表的构造方法与上同。2.(1) 证明：任取，和*可交换是可交换的。(2) 任取 和*可结合是可结合的。3.012345001234511234502234501334501244501235501234 证明： 与都只有一个二元运算，故为同型的。 与定义域大小相同，具备构成双射函数的条件。 构造双射函数由上图可知，像的运算=运算的像所以与是同构的。6.5第155页1.（1）半群（2）半群（3）半群（4）独异点，么元0（5）不是半群，取a=b=1,c=2，则不满足结合律（6）不是半群，因为|不是二元运算；（7）半群（8）独异点，么元0（9）半群（10）独异点，么元为恒等关系；（11）独异点，么元为a2.（1）二元运算表如下图所示：GCD1234681224111111111212122222311313133412142444612326266812142848121234641212241234681224（2）, 其中。（假定为丛X到X的双射函数）解：X到X有6个双射函数，分别用表示，设 构造运算表如下：第七章 图论6.1第164页1.画出图的图示，指出其中哪些图是简单图。（1）不是简单图。（2）不是简单图。（3）是简单图。2.写出图7-8的抽象数学定义。（1）解：，其中，（2）解：，其中， ， 3.证明：在n阶简单有向图中，完全有向图的边数最多，其边数为。证明：简单有向图是没有自环，没有平行边的有向图，只要两个不同的结点之间才能有边。完全有向图是每个结点的出度和入度都是n-1的简单有向图，也就是每个结点都有到其他所有结点的边，因此，完全有向图的边数最多。在完全有向图中，所有结点的出度之和为n(n-1)，所有结点的入度之和为n(n-1)，设边的个数为m，由握手定理可知，2m= n(n-1)+ n(n-1)，即m= n(n-1)，得证。4.证明：3度正则图必有偶数个结点。证明：设三度正则图的结点个数为n，那么所有结点的度数之和为3n，由握手定理可知，边的个数为3n/2=1.5n，由于边的个数一定是整数，因此，n为偶数。得证。5.在一次集会中，相互认识的人会彼此握手，试证明：与奇数个人握手的人数是偶数个。证明：设集会上的人一共有m个，可分为两部分，一部分为与奇数个人握手的人，设为x个，另一部分为与偶数个人握手的人，为m-x个。由于握手是相互的，即一次握手，两个人握手的次数都加1，一共加2，因此，集会上所有人的握手次数之和为偶数。与偶数个人握手的人，这些人的握手次数之和为（其中，都是偶数），为偶数。与奇数个人握手的人，这些人的握手次数之和为（其中，为基数），由于所有人的握手次数之和偶数，因此也要为偶数，即又因为即，因此x为偶数，即与奇数个人握手的人是偶数个，得证。6.证明：图7-7中的两个图同构。证明：首先，给这两幅图标上对应的结点编号，如下两个图的结点和边的数目都相同。假设函数，左图中相邻的结点是1和4，1和5，1和6，2和4，2和5，2和6，3和4，3和5，3和6，对应的像点1和4，1和2，1和6，5和4，5和2，5和6，3和5，3和2，3和6在右图中也相邻，因此，两图同构。7.证明：在任意六个人中，若没有三个人彼此认识，则必有三个人彼此都不认识。证明：分三种情况：（1）任何一个人最多认识另外一个人将相互认识的两个人分成一组，则至少可以分3组，每组取一个人，则这三个必不认识。（2）任何一个人最多认识另外两个人最糟糕的情况是当每个人都认识另外两个人时，若认识的人之间画一条线可以构成一个六边形，取不相邻的三个点即是不认识的。（3）任何一个人最多认识另外的三个人不妨设点A与B,C,E认识（用实线连接）。因为B,C,E之间只有有两个人认识就不满足任何三个人都不认识的条件，比如B,C认识画一条实线，那么A,B,C就相互认识，与已知矛盾。所以B,C,E是所求的三个互补认识的人。（4）任何一个人最多认识两外4或5个人该情况与（3）类似，所求的人即与A认识的两外4或5个人中的三个人。证毕。8.证明：图7-9的两个图不同构。证明：给这两幅图标上对应的结点编号，如下：两个图的点数和边数相同。假设函数：易证： a）中的子图，与b）中的子图，同构。 a）中的子图，与b）中的子图，同构。除这两个子图以外，对应a）中的子图，在b）无中对应的同构图。因此a）和b）两个图不同构。9图7-10的两个图是否同构？说明理由。解：对于图b）中的点，其出度为：，入度：。而在a)图中不存在这样的结点。因此这两个图不同构。10证明：任何阶大于1的简单无向图必有两个结点的度数相等。证明：考虑一个有n个结点的连通图（如果有一个孤立结点，去掉孤立结点考虑联通子图）。因为是无向连通图，每个结点的最大度数是n-1，最小度数是1。即对n个点赋值，共n-1种取值，由抽屉原理，必有两个结点的取值相同，即必有两个点的度数相同。11设n阶无向图G有m条边，其中个结点的度数为k，其余结点的度数为k+1，证明：。证明：由题意，结点数为n，由总边数建立关系：，由此可得：。7.2第168页1画出的所有不同的子图，并说明其中哪些是生成子图，找出互为补图的生成子图。解：其中，（1）和（7），（2）和（6），（3）和（5），（4）中的后两个图可以构成互补的生产子图。2设是完全有向图。证明：对于的任意非空子集，是完全有向图。证明：（1）当中只有一个结点时，是完全有向图。（2）当中有多于一个结点时，对其中任意两个结点是的子集，即。因为图G是完全有向图，因此间存在两条有向边和。是由非空子集生成的子图，故，即中任意两个结点间存在两条有向边，故是完全有向图。3画出图7-15的两个图的交、并和环和。解：交： 并： 环和：4设G是任意6阶简单无向图，证明：G或必有一个子图是3阶无向图。证明：取G或任意取三个点，取与这三个点相关联的变构成一个3阶的无向子图。5我们称与补图同构的简单无向图为自补图。证明：每个自补图的阶能够被4整除或被4整除余数为1。证明：设图的顶点数为n，Kn的边数为,由自补图的定义知该图与其子图的边数相同（同构），故其边数为，由该数是整数得：，。故每个自补图的阶能够被4整除或被4整除余数为1。7.3第173页1考虑图7-21（1）从A至F的路径有多少条？找出所有长度小于6的从A至F的路径。解：A到F的路径有无数条。长度小于6的有24条。（c f h:4,c g h:4, c e i:4, b d e f h:2, b d e g h:2, b d i:4）（2）找出从A至F的所有简单路径。解：12条。(c f h, c g h, c e I, b d e f h, b d e g h, b d i),还有一个自环，需乘以2.（3）找出从A至F的所有基本路径。解：6条。(c f h, c g h, c e I, b d e f h, b d e g h, b d i)（4）求出从A至F的距离。求出该图的直径。解：距离为3。直径为3。（5）找出该图的所有回路。解：AaA, AbDdEeBcA, BeEiFhCgB; BgCfB; AbDdEiFhCgBcA; BeEiFhCfB;2证明：图7-21中基本路径必为简单路径。证明：基本路径要求途经的顶点不重复，简单路径要求途经的边不重复。在图7-21中，对于所有的基本路径，边不重复出现。所以基本路径必是简单路径。3考虑图7-22（1）对于每个结点，求。解： （2）找出所有强分支、单向分支和弱分支。解：强分支7个，分别是单项分支4个，分别是弱分支3个，分别是4设是任意无向图（有向图）G的三个任意结点，以下三个公式是否成立？如果成立，给出证明；如果不成立，举出反例。（1），并且等号成立，当且仅当。解：成立。当时，距离必定大于1。（2）解：成立。因为无向图是无方向的。5. 证明：有向图的每个结点和每条边恰处于一个弱分支中。反证法：若任意结点V处于两个或两个以上的弱分支中，不妨设两个弱分支为G1, G2, 则G1, G2是G的极大联通子图。设，又,故联通。这与G1, G2是极大联通子图矛盾，故命题得证。6. 有向图的每个结点（每条边）是否恰处于一个强分支中？是否恰处于一个单向分支中？解：有向图中的每个结点处于一个强分支中，而边不一定。有向图的结点和边可能出现在两个单向分支中。图见书上（P141 图7-18）7. 证明同阶的回路必同构。证明：同阶表明两个图的顶点个数相同，设为V; 又联通二度正则图称为回路。即两个图的每个顶点的度数相同为2. 边数为2V/2 = V,相同。由于两个图的顶点数，边数相同，且每个顶点的度数均为2，故两个图同构。9. 设G是弱联通有向图，如果对于G的任意结点v, ,则G恰有一条有向回路。试给出证明。证明：因为G是弱联通有向图，不妨设一条极大单向联通子图：因为: , 所以对，。若，则与极大联通子图矛盾，故V必为之一。又假设有两条以上的回路（反证法），不妨设有两条，则这两条回路上所有点的出度为1，而要使这两条回路联通，则至少其中有一个点的出度大于1，这与矛盾。故G恰有一条会向回路。10. 设G为n阶简单无向图，对G的任意结点v, ，证明G是联通的。证明：任取, 因为, 故至少存在个点与相连，最多还剩余（除去剩余的点）。故对于至少存在一个与连接的点与相连，因此与联通。由与选取的任意性，G联通。11. 证明：对于小于或等于n的任意正整数k, n阶连通无向图有k阶连通子图。证明：n阶连通无向图，则n个顶点中的任意点与其他顶点均可达。取其中的k个顶点也满足该性质，故存在k阶连通子图。7.4第181页1. 解：根据图7-26得邻接矩阵为：到：长度为1的基本路径为：长度为2的基本路径为：长度为4的基本路径为：，,2. 解：（1）对于n=1,2,6，试计算矩阵中的各元素。，（2），（3）试求出图中G1和G2中的所有基本循环。对于和，表示结点()上长度为k的循环的个数。3. 对于图7-26中的有向图，试求出邻接矩阵A的转置,列出矩阵的元素值，并说明它们的意义。解：表示有向图逆图的邻接矩阵，即原图中如果有第i个结点到第j个结点长度为1的路径，则中第j行第i列为1；第i个结点和第j个结点引出的边，可以同时终止于某些结点，这些结点的个数为中第i行第j列的元素值。从某些结点引出的边，可以同时终止于第i个结点和第j个结点，这些结点的个数为中第i行第j列的元素值。中第i行第j列对应元素为1表示从第i个结点和第j个结点引出的边，可以同时终止于某些结点；为0表示第i个结点和第j个结点引出的边，不可以同时终止于某个结点。4. 对于nxn的布尔矩阵A，试证明：其中是nxn的单位矩阵，并且有。再证明：对于任何正整数,都有证明：（1），若该矩阵中的, 则存在使得且，即, 故。又， (因为相当于每个顶点到自己的边，不改变该顶点到其他顶点的边)，因此有：= , 故问题一得证。（2）用数学归纳法证明：当n=2时成立。假设当n=k是成立，则有：当n=k+1时， 故命题成立。5.给定简单有向图，并且有。设是的邻接矩阵。试证明：根据第1题中所得到的结果能够把路径矩阵表示成。证明：对于有向图的路径矩阵：，而对于第一题有：，故有：，由第4题得到：，故有：，得证。6. 图7-27给出一个简单有向图。试求出该图的邻接矩阵A，并求出其路径矩阵。解：，=7. 使给出图7-25中的有向图的距离矩阵。意味着什么？解：, 表示有一条到的边。8. 试求出第2题中的图G1和G2的距离矩阵。解：, 9. 如何才能从一个距离矩阵中求得一个路径矩阵呢？证明：对于任意结点和（），由题意，因此从到必定存在一条长度不为0的路径，由结点选取的任意性得：任何两个结点均是联通的。故G的强联通的有向图。从距离矩阵求路径矩阵：将距离矩阵中不为0的值变为1，即可得到。10. 试确定图7-25所示的图是否是强分支。解：对图7-25由距离矩阵求得的路径矩阵为：，由路径矩阵知该图不是强分支。7.5第184页1. 解：a), b), c)是欧拉图，d), e), f)不是欧拉图。2.如果和是可运算的欧拉有向图，则仍是欧拉有向图。这句话对吗？如果对，给出证明，如果不对，举出反例。证明：不对,不能保证连通.4.设G是平凡的连通无向图，证明：G是欧拉图，当且仅当G是若干个边不相交的回路的并。证明：充分性，当进行若干个不相交的回路的并运算后，每个结点都是偶结点，因此G是欧拉图。必要性，对于G是欧拉图，则G必定有欧拉闭路。如果某个结点的度数大于2，可以对结点的环路进行分解，分解为多个小的环路的并。7.6第186页1.图7-34是不是二部图？如果是，找出其互补结点子集。解：是，互补结点子集是：,。2.如何由无向图G的邻接矩阵判断G是不是二部图？解：设G的邻接矩阵为，计算，。其中如果矩阵的对角线出现了基数，则G不是二部图。如果所有的矩阵（包括矩阵）的回路长度都是偶数，则是二部图。3.举出一个二部图的例子，它不满足定理7.6.3的条件，但是存在完美匹配。解：如第一题的例子，二部图为：5317642该图中不满足定理7.6.3的条件（对于V1，在V2中至少有2个结点与其相邻，但是在V2中，各结点最多有有2个结点与V1中结点相邻），但是该图是完美匹配，因为匹配数为3（=）（如， ，）4.证明：n阶简单二部图的边数不能超过。证明：对于简单二部图，当为完全二部图时边数最多，边数为，又，当即时，有最大值，故边数取整，故边数不能超过。得证。5. 解：可能，如下图：6. 解：7. 图7-35是否存在,到,的完美匹配？如果存在，指出它的一个完美匹配。解：存在。如：，。7.7第192页1.对于下列情况，验证欧拉公式n-m+k=2(1)图7-45中的多边形的图。解：对a)点数7，面的个数3，边的个数8，7+3-8=2，成立。对b)顶点个数8，面的个数3，边的个数9，8+3-9=2，成立。(2)一个具有个结点的无向边，它描述了个正方形的网络，例如棋盘等。解：顶点个数为，面的个数为，边的个数为，+-2=2，成立。2.试证明：图7-42b中的库拉图斯基图是个非平面图。证明：对于基本环路：,考虑和在环的内侧，直线必定在外侧。对于直线和必定相交。故该图是非平面图。3. 画图所有不同构的6阶非平面图。解：根据分析图至少有9条边，最多为15条边。所有情况如下图：4.试用库拉斯基定理证明：图7-48中的图是个非平面图。证明：图7-48中村子一个子图与阶数为6的库拉斯基图同构。将图7-48变形得到：其中的由,构成的子图与阶数为6的库拉斯基图同构。故该图是非平面图。5. 图7-49给出一个多边形的图，试构成该图的对偶。解：对偶图如下：7.8第204页1.画出所有不同构的一、二、三、四、五、六阶树。解：一阶：二阶：三阶：四阶(2)：五阶(3)：六阶(6)：2.如何由无向图G的邻接矩阵确定G不是树？解：根据“G不含回路而且有n-1条边则G是树”可以得出图G是一棵树的判定条件如下：(1)无线图G的邻接矩阵的n次幂中，对角线上全是0（说明不存在回路）。（2）邻接矩阵中1的个数的总数为2(n-1),说明边的个数为n-1。邻接矩阵同时满足上面两个条件可以判断图G是树，如果不同时满足，则判断不是树。3.设和是树T的两个不同的结点，从至的基本路径是T中最长的基本路径。证明：证明：反证法假设或有一个结点的度数大于1，不妨设,则必然存在一个与相连，由树的定义知不在至的路径中（否则构成了环）。设至的路径长度为，则到的距离为，这与至的基本路径是T中最长的基本路径矛盾。故。4.。解：a)b)7. 证明：任何二叉树有基数个结点。证明：在二叉树中，任何结点的出度不是0，就是2；假设出度为2的结点有x个，则该二叉树的出度之和为2x；设二叉树共有n个结点，这些结点中除了根结点的入度为0，其余结点的入度都为1，因此，所有结点的入度之和为n-1。由图的性质，可知二叉树的出度之和与入度之和相等。即n-1=2x， n=2x+1，因此，无论x如何取值，二叉树的结点总数n都是基数。得证。9. 证明：n阶二叉树的叶子结点数目为(n+1)/2，其高度h满足log2(n+1)-1h (n-1)/2证明：（1）在二叉树中，出度为0的结点是叶子结点，出度为2的结点是分支结点，设分支结点个数为x，由上题证明过程可知，n=2x+1, x=(n-1)/2。因此，叶子结点的个数为n-x=(n+1)/2。（2）n阶二叉树的叶子结点有(n+1)/2个，分支结点有(n-1)/2个。利用(n-1)/2个结点构造一棵一元或二元树，设树高为m，则h=m+1。考察(n-1)/2个结点构造的一棵一元或二元树，树高最大的情况是一元树，高度为(n-1)/2-1，因此，h最大值是(n-1)/2-1+1=(n-1)/2。树高最小的情况是构造了一棵满二叉树，满二叉树的高度x和结点个数(n-1)/2满足关系2x+1-1=(n-1)/2，解得x=log(n+1)-2，因此h最小值是log(n+1)-1。因此，log2(n+1)-1h (n-1)/2。10.如何由有向图G的邻接矩阵确定G是不是有向树？解：根据有向树的判定定义：仅一个结点的入度为0，其余结点的入度均为1的连通有向图。如果G是有向树，则其邻接矩阵满足：（1）有且仅有一列全为0。（2）其余的列有且只有一个1。否则有向图不是有向树。11. 找出叶的权分别为2，3，5，7，11，13，17，19，23，29，31，37和41的最优叶加权二叉树，并求其叶加权路径长度。解：对于2,3,5,7,11,13,17,19,23,29,31,37,41，先组合两个最小的权2+3=5，得5,