4~离散数学习题解答习题六(第六章 图论)6

《4~离散数学习题解答习题六(第六章 图论)6》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学习题解答习题六（第六章图论）1．从日常生活中列举出三个例子，并由这些例子自然地导出两个无向图及一个向图。[解]①用V代表全国城市的集合，E代表各城市间的铁路线的集合，则所成之图G=（V，E）是全国铁路交通图。是一个无向图。②V用代表中国象棋盘中的格子点集，E代表任两个相邻小方格的对角线的集合，则所成之图G=（V，E）是中国象棋中“马”所能走的路线图。是一个无向图。③用V代表FORTRAN程序的块集合，E代表任两个程序块之间的调用关系，则所成之图G+（V，E）是FORTRAN程序的调用关系图。是一个有

2、向图。2．画出下左图的补图。图[解]左图的补图如右图所示。v1′v2′v3′v4′v5′v6′v6v13．证明下面两图同构。图G′图Gv5v4v3v2[证]存在双射函数j:V→V′及双射函数y:E→E′j(v1)=v1′j(v1，v2)=(v1′，v2′)j(v2)=v2′j(v2，v3)=(v2′，v3′)162j(v3)=v3′j(v3，v4)=(v3′，v4′)j(v4)=v4′j(v4，v5)=(v4′，v5′)j(v5)=v5′j(v5，v6)=(v5′，v6′)j(v6)=v6′j(v6，v1)

3、=(v6′，v1′)j(v1，v4)=(v1′，v4′)j(v2，v5)=(v2′，v5′)j(v3，v6)=(v3′，v6′)显然使下式成立：y(vi，vj)=(vi,vj′)Þj(vi)=vi′∧j(vj)=vj′(1≤i·j≤6)于是图G与图G′同构。v1v2v3v4v88v78v58v68v4¢v1¢v2¢v7¢v6¢v8¢v5¢v3¢v1v2v3v4v58v1¢v2¢v3¢v4¢v584．证明（a），（b）中的两个图都是不同构的。GG′GG′图G中有一个长度为4的圈v1v2v6v5v1，其各顶点的

4、度均为3点，而在图G′中却没有这样的圈，因为它中的四个度为3的顶点v1¢，v5¢，v7¢，v3¢不成长度的4的圈。图G′中有四个二度结点，v6¢，v8¢，v4¢，它们每个都和两个三度结点相邻，而G中一个区样的结点都没有。在（b）中，图G¢中有一2度结点v3¢，它相邻的两个项点v2¢，v4¢的度均为4，而在图G中却没有这样的点。5．一个图若同构于它的补图，则称此图为自补图。在满足下列条件的无向简单图中：1)给出一个五个结点的自补图；2)有三个或一结点的自补图吗？为什么？3）证明：若一个图为自补图，则它对应的完

5、全图的边数不清必然为偶数。162[解]1)五个结点的自补图如左图G所示GGbedcaaebcd同构函数j:V→V及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)的结论，不可能有自补图。（b）有五个结点的自补图。1）中的例子即是一个五个结点的自补图。3）证：一个图是一个自补图，则它

6、对应的完全图的边数必为偶数。因为若一个图G是自补图，则G∪=对应的完全图，而且E∩=φ，G现同构，因此它们的边数相等，即

7、E

8、=

9、

10、，因此对应的完全图的边数

11、E*

12、=

13、E

14、+

15、

16、=2

17、E

18、，是偶数。实际上，n个项点（n＞3）的自补图G，由于其对应的完全图的边数

19、E*

20、=，因此有=2

21、E

22、，为偶数。这里n≥4。对于所有大于或等于4的正整数，都可表达成n=4k，4k+1，4k+2，4k+3的形式，这里k=1，2，…。其中只有n=4k，4k+1，才能使为偶数，所以自补图的项点数只能是4k或4k+1形式，（k∈N）

23、6．证明在任何两个或两个以上人的组内，总存在两个人在组内有相同个数的朋友。162[证]令上述组内的人的集合为图G的项点集V，若两人互相是朋友，则其间联以一边。所得之图G是组内人员的朋友关系图。显然图G是简单图，图中项点的度恰表示该人在组内朋友的个数，利用图G，上述问题就抽象成如下的图认论问题：在简单图G中，若

24、V

25、≥2，则在G中恒存在着两个项点，v1，v2∈V，使得它们的度相等，即deg(v1)=deg(v2)。其证明如下：若存在着一个项点v∈V，使得deg(v)=0，则图G中各项点的度最大不超过n-2。因

26、此n个项点的度在集合{0，1，2，…，n-2}里取值，而这个集合只有n-1个元素，因此，根据鸽笼原理，必有两个项点的度相同。若不存在一个度为零的项点，则图G中各项点的度最大不超过n-1。因此n个项点的度在集合{1，2，…，n-1}中取值，这个集合只有n-1个元素，因此，根据鸽笼原理，必有两具项点的度相同。ADEFCB7．设图G的图示如右所示：1)找出从A到F的所有初级路；2）找出从A到F的所有简单路；3）求由A到