《交大版离散的数学结构标准答案》由会员分享，可在线阅读，更多相关《交大版离散的数学结构标准答案（35页珍藏版）》请在金锄头文库上搜索。
1、离散数学辅助教材概念分析结构思想与推理证明离散数学习题解答习题六 （第六章 图论）1从日常生活中列举出三个例子，并由这些例子自然地导出两个无向图及一个向图。解 用V代表全国城市的集合，E代表各城市间的铁路线的集合，则所成之图G=（V，E）是全国铁路交通图。是一个无向图。V用代表中国象棋盘中的格子点集，E代表任两个相邻小方格的对角线的集合，则所成之图G=（V，E）是中国象棋中“马”所能走的路线图。是一个无向图。用V代表FORTRAN程序的块集合，E代表任两个程序块之间的调用关系，则所成之图G+（V，E）是FORTRAN程序的调用关系图。是一个有向图。2画出下左图的补图。 图解 左图的补图如右图所
2、示。v1v2v3v4v5v6v6v13证明下面两图同构。图G图Gv5v4v3v2 证 存在双射函数j:VV及双射函数y : EEj (v1)=v1j (v1，v2)=(v1，v2)j (v2)=v2j (v2，v3)=(v2，v3)j (v3)=v3j (v3，v4)=(v3，v4)j (v4)=v4j (v4，v5)=(v4，v5)j (v5)=v5j (v5，v6)=(v5，v6)j (v6)=v6j (v6，v1)=(v6，v1)j (v1，v4)=(v1，v4)j (v2，v5)=(v2，v5)j (v3，v6)=(v3，v6)显然使下式成立： y (vi，vj)=(vi,vj) j
3、(vi)=v ij (vj)=vj (1ij6)于是图G与图G同构。v1v2v3v4v88v78v58v68v4v1v2v7v6v8v5v3v1v2v3v4v58v1v2v3v4v584证明（a），（b）中的两个图都是不同构的。GGGG图G中有一个长度为4的圈v1v2v6v5v1，其各顶点的度均为3点，而在图G中却没有这样的圈，因为它中的四个度为3的顶点v1，v5，v7，v3不成长度的4的圈。图G中有四个二度结点，v6，v8，v4，它们每个都和两个三度结点相邻，而G中一个区样的结点都没有。在（b）中，图G中有一2度结点v3，它相邻的两个项点v2，v4的度均为4，而在图G中却没有这样的点。5一个
4、图若同构于它的外图，则称此图为自补图。在满足下列条件的无向简单图中： 1) 给出一个五个结点的自补图；2)有三个或一结点的自补图吗？为什么？3）证明：若一个图为自补图，则它对应的完全图的边数不清必然为偶数。解 1) 五个结点的自补图如左图G所示GGbedcaaebcd同构函数j : VV及y : E如下： j (a)=ay(a，b)=(a，c) j (b)=cy(b，c)=(c，e) j (c)=ey(c，d)=(e，d) j (d)=by(d，e)=(b，d) j (e)=d(e，a)=(d，a)2)（a）没有三个结点的自补图。因为三个结点的完备图的边数为=3为奇数，所以由下面3)的结论，不
5、可能有自补图。（b）有五个结点的自补图。1）中的例子即是一个五个结点的自补图。3）证：一个图是一个自补图，则它对应的完全图的边数必为偶数。因为若一个图G是自补图，则G=对应的完全图，而且E=，G现同构，因此它们的边数相等，即|E|=|，因此对应的完全图的边数|E*|=|E|+|=2|E|，是偶数。实际上，n个项点（n3）的自补图G，由于其对应的完全图的边数|E*|=，因此有=2|E|，为偶数。这里n4。对于所有大于或等于4的正整数，都可表达成n=4k，4k+1，4k+2，4k+3的形式，这里k=1，2，。其中只有n=4k，4k+1，才能使为偶数，所以自补图的项点数只能是4k或4k+1形式，（k
6、N）6证明在任何两个或两个以上人的组内，总存在两个人在组内有相同个数的朋友。证 令上述组内的人的集合为图G的项点集V，若两人互相是朋友，则其间联以一边。所得之图G是组内人员的朋友关系图。显然图G是简单图，图中项点的度恰表示该人在组内朋友的个数，利用图G，上述问题就抽象成如下的图认论问题：在简单图G中，若|V|2，则在G中恒存在着两个项点，v1，v2V，使得它们的度相等，即deg(v1)=deg(v2)。其证明如下：若存在着一个项点vV，使得deg(v)=0，则图G中各项点的度最大不超过n-2。因此n个项点的度在集合0，1，2，n-2里取值，而这个集合只有n-1个元素，因此，根据鸽笼原理，必有两
7、个项点的度相同。若不存在一个度为零的项点，则图G中各项点的度最大不超过n-1。因此n个项点的度在集合1，2，n-1中取值，这个集合只有n-1个元素，因此，根据鸽笼原理，必有两具项点的度相同。ADEFCB7设图G的图示如右所示： 1) 找出从A到F的所有初级路；2）找出从A到F的所有简单路；3）求由A到F的距离。解 1）从A到F的初级路有7条P1 : (A，B，C，F)，P2 (A，B，C，E，F)，P3 : (A，B，E，F)P4 : (A，B，E，C，F)，P5 : (A，D，C，E，F)，P6 : (A，D，E，C，F)P7 : (A，D，E，B，C，F)。 2）从A到F的简单路有9条 除
8、了上述1）中7条外，不有P8 : (A，D，E，C，B，E，F)P9 : (A，D，E，B，C，E，F)。 3）从A到F的距离为3。 由图可看出，显然从A到F，一步不可能到达，二步也不可到达；但有长度为3的路，比如P1，P3，P5等能从A到F，故从A到F的距离为3。8在下面的图中，哪此是边通图？哪些是简单图？ （a） (b) (c)解 （1）图（2）与图（b）不连通，它们能分成两个边通支。所以只有图（c）是连能图。（2）图（c）是简单图，图为它显然无平等边，无自环。图（a）、（b）是多重图（a）有平行边（b）有自环。9求出所有具有四个结点的简单无向连通图。解 在不同构的意义下，具有四个结点的简
9、单无向连通图共有6个。如下面所示：G1G2G3G4G5G6G6G5G4G2（实际上，具有四个结点的简单图共有11个，这可由P定理得证。参见卢开澄的组合数学一算法与分析上册P241-P244）。10设G是一个简单无向图，且为（n，m）图，若证明G是连通图。证 用反证法。假若简单无向图G不是连通图，那么G必可成K（2）个连通分支G1，G2，Gk，每个连通分支Gi（1ik）都是一个简单无向图，因此它们分别为（n1，m1），（n2，m2），（nk，mk）图显然有n=n1+n2+nk，m=m1+m2+mk，且nin-1（1ik）于是有m=m1+m2+mk =(n-1)(n1-1)+(n2-1)+(nk-
10、1)=(n-1)(n1+n2+nk)-k)= (n-1)(n-k)(n-1)(n-2) (k2)这与已知M（n-1）(n-2)矛盾。因此假设错误，G是连通图。11设G=（V，E）是无向完全图（无自环），|V|=n1） 求G中有多少初级圈？2） 设eE，求含有e的初级圈有几个？3） 设u，vV，uv，求由u到v有几条初级路？解 1）在一个有n个结点的无向完全图（无自环）中，构成一个初级圈，至少需3个结点，至多有n个结点，故G中初级圈的个数为即将从n个结点中选出的k个结点进行排列，然后除去重复：每个排列的倒排列（除2）；长为k的圈排列可形成k个线排列（除k）。2）含有边e的初级圈为即，从u到v的直
11、接边（完全图，该边存在）是一条；再将该直接边加到其它初级路里，就构成了含边（u，v）的初级圈，从而由2)可得如上数值。12试证在简单有向图中1) 每个结点及每条边都属于且只属于一个弱分图；2) 每个结点及每条边都至少属于一个单向分图。证 1）有向图中的弱连通性建立了G中结点集合V上的等价关系，因此构成了V上的一个划分；同时，还建立了边集上的一个划分。因此，每一个弱连通支就是一个“划分块”。设G1，G2，Gk为G的所有弱连通分图，则有：V（G）=V（G1）V（G2）V（Gk）E（G）=E（G1）E（G2）E（Gk）并且，当ij时，V（Gi）V（Gj）=，E（Gi）E（Gj）=。因此，每个结点及每
12、条边都属于且只属于一个弱图。 2）有向图中的单向连通性建立了G中结点集合V上的一个相容关系，因此构成了V上的一个覆盖；同时，还建立了边集上的一个覆盖；每一个单向分图就是一个“覆盖快”。设G1，G2，Gk为G的所有单向分图，则有V（G）=V（G1）V（G2）V（Gk）E（G）=E（G1）E（G2）E（Gk）因此，每个结点及每条边都至少属于一个单向分图。13试用有向图描述出下述问题的解法路径：某人m带一条狗d，一只猫c和一只兔子r过河，没有船，他每次游过河时只能带一只动物，当没有人管理时狗和兔子不能相处，猫和兔子也不能相处。在这些条件的约束下，他怎样才能将这三只动物从北岸带往南岸？解 将人，狗，兔
13、中任意几种在一起的情况看作是一种状态；一个布局是一个二元组，由两个互补的状态构成，二元组的前者表示河北岸的状态，后者表示河南岸的状态。初始布局为（pdcr，），终止布局为（，pdcr）安全布局有十种，不安全布局有六种，它们是：（dr，pc），（cr，pd），（dcr，p），（pc，dr），（pd，cr），（p，dcr）。pdc,rpdcr,dc,prc,pdrpcr,ddpc,rpdr,cpr,dc,pdcr按题意构造有向图，其解法路径如下：14求下列图中的所有强连通支，单向连通支，弱连通支。v5v1v10v9v8v7v4v3v2v6 解 1）有六个强连通支，它们是：G1=(v1，v2，v3，v9，v10，(v1，v2)，(v2，v9)，(v9，v10)，(v10，v1)，(v2，v3)，(v3，v9)G2=(v4，)，G3=(v8，)，G4=(v7，)，G5=(v5，(v5，v5)，G6=(v6，)。2）有四个单向连通支，它们是：G1=(v1，v2，v3，v4，v9，v10，(v1，v2)，(v2，v9)，(v9，v10)，(v10，v1)，(v2，v3)，(v3，v9)，(v3，v4)，G
