哈工大集合论习题课-第五章 图的基本概念习题课(学生).doc

《哈工大集合论习题课-第五章 图的基本概念习题课(学生).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章图的基本概念习题课11.画出具有6、8、10、…、2n个顶点的三次图；是否有7个顶点的三次图？2.无向图有21条边，12个3度数顶点，其余顶点的度数均为2，求的顶点数。解：设图的顶点为，根据握手定理：，有，得。3.下列各无向图中有几个顶点？（1）16条边，每个顶点的度为2；（2）21条边，3个4度顶点，其余的都为3度数顶点；（3）24条边，各顶点的度数相同。解：设图的顶点为，根据握手定理：（1），即；所以，即有16个顶点。（2），即，所以。（3）各点的度数为，则，即，于是①若，；②若，；③若，；④若，；⑤若，；⑥若，；⑦若，；⑧若，；13⑨若，；⑩若，。4．设图中

2、9个顶点，每个顶点的度不是5就是6。证明中至少有5个6度顶点或至少有6个5度顶点。证：由握手定理的推论可知，中5度顶点数只能是0，2，6，8五种情况，此时6度顶点数分别为9，7，5，3，1个。以上五种情况都满足至少5个6度顶点或至少6个5度顶点的情况。5．有个药箱，若每两个药箱里有一种相同的药，而每种药恰好放在两个药箱中，问药箱里共有多少种药？[就是求一个完全图的边数]6.设是有个顶点，条边的无向图，各顶点的度数均为3。则（1）若，证明同构意义下唯一，并求；（2）若，证明在同构的意义下不唯一。分析：在图论中，对于简单无向图和简单有向图，若涉及到边与顶点的问题，握手定理是

3、十分有用的。解：（1）由于各顶点的度数均为3，现在有个顶点，条边，所以由握手定理知：，即，故；又，故，则。即，，此时所得的无向图如图1所示，该图是4个顶点的简单无向图中边最多的图，即为无向完全图。对于4个顶点的完全图，在同构意义下，4个顶点的完全图是唯一的。（2）若，由握手定理：，即。故，此时有，且每个顶点的度数为3；此时对于简单无向图，6个顶点，9条边及每个度数为3的有如图2所示两个非同构的图；与是非同构的图，所以，度数为3的无向图在同构的意义下是不唯一的。13（a）(b)图1图27.已知阶简单图中有条边，各顶点的度数均为3，又，试画出满足条件的所有不同构的。解：由握

4、手定理：，又，即。故，即，。此时有，且每个顶点的度数都为3，则不同构的无向图有两个，如图3所示。图38．9个学生，每个学生向其他学生中的3个学生各送一张贺年卡。确定能否使每个学生收到的卡均来自其送过卡的相同人？为什么？解：否，因为不存在9（奇数）个顶点的3－正则图习题课2例3设为正整数，则（1）为何值时，无向完全图是欧拉图？为何值时为半欧拉图？（2）为何值时为欧拉图？（3）为何值时为哈密整图？13（3）为何值时，轮图为欧拉图？证：（1）一般情况下，不考虑无向图。因此因为各顶点的度均为，若使为欧拉图，必为偶数，因而必为奇数。即为奇数时，完全图是欧拉图。若或为奇数时，是半欧

5、拉图。（2）当均为偶数时，为欧拉图。（3）当时，为哈密整图。（4）设为轮图，在中，有个顶点的度为3，因而对于任意取值，轮图都不是欧拉图。例1判断图5所示的图是否为哈密顿图，若是写出哈密顿回路，否则证明其不是哈密顿图。(a)(b)图3图4例2给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点和，均有。例3试求中不同的哈密顿回路的个数。例4(1)证明具有奇数顶点的偶图不是哈密顿图；用此结论证明图8所示的图不是哈密顿图。13(2)完全偶图为哈密顿图的充分必要条件是什么？证：(1)设是一个具有奇数顶点的偶图，则的顶点集有一个二划分，即且有。不妨设，则有。由哈密顿图的必

6、要条件可知：不是哈密顿图。题中所给的图中无奇数长的回路，因而此图是偶图。而且此图中有13个顶点，因此它不是哈密顿图。(2)若，有(1)可知不是哈密顿图；若，同理有不是哈密顿图。故是哈密顿图时只有，即。若，则，由定理知：是哈密顿图。例5菱形12面体的表面上有无哈密顿回路？例6设是连通图且顶点数为，最小度数为，则中有一长至少为的路。分析:采用最长路法，设连通图的最长路为且。再看这条路的端点，端点只能与上的顶点相邻，这样就可以构成一个回路，对于回路外的顶点，因为仍与此回路上的某些顶点相邻，所以可以把这个顶点连到回路上，然后再打开回路，显然这时有一条路比假设时的路更长了，所以假

7、设不成立。证：假设中的最长路为：，其长度为。因为，，所以存在，使与在中相邻，得一长为的回路：。又因为连通，且的顶点数，故存在与回路上13相邻，则把回路在处断开，并把连入回路中，得到一条长为的路，矛盾。所以中有一长至少为的路。例7证明：彼德森()图不是哈密顿图。例8某工厂生产由6种不同颜色的纱织成的双色布。双色布中，每一种颜色至少和其他3种颜色搭配。证明：可以挑出3种不同的双色布，它们含有所有6种颜色。证：用6个不同的点分别表示6种不同颜色的纱，两个点间联一条线当且仅当用这两点所表示的两种不同颜色的纱织成一种双色布。于是，我们得到一个有6个