《哈工大集合论习题课-第五章 图的基本概念习题课(学生).doc》由会员分享，可在线阅读，更多相关《哈工大集合论习题课-第五章 图的基本概念习题课(学生).doc（17页珍藏版）》请在三一文库上搜索。
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）各点的度数为，则，即，于是 若，； 若，； 若，； 若，；精品. 若，； 若，； 若，； 若，； 若，； 若，。4设图中9个顶点
2、，每个顶点的度不是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）若，证明在同构的意义下不唯一。分析：在图论中，对于简单无向图和简单有向图，若涉及到边与顶点的问题，握手定理是十分有用的。解：（1）由于各顶点的度数
3、均为3，现在有个顶点，条边，所以由握手定理知：，即，故；又，故，则。即，此时所得的无向图如图1所示，该图是4个顶点的简单无向图中边最多的图，即为无向完全图。对于4个顶点的完全图，在同构意义下，4个顶点的完全图是唯一的。精品.（2）若，由握手定理：，即。故，此时有，且每个顶点的度数为3；此时对于简单无向图，6个顶点，9条边及每个度数为3的有如图2所示两个非同构的图；与是非同构的图，所以，度数为3的无向图在同构的意义下是不唯一的。 （a） (b)图1 图27.已知阶简单图中有条边，各顶点的度数均为3，又，试画出满足条件的所有不同构的。解：由握手定理：，又，即。故，即，。此时有，且每个顶点的度数都为
4、3，则不同构的无向图有两个，如图3所示。 图389个学生，每个学生向其他学生中的3个学生各送一张贺年卡。确定能否使每个学生收到的卡均来自其送过卡的相同人？为什么？精品.解：否，因为不存在9（奇数）个顶点的3正则图习题课2例3设为正整数，则（1）为何值时，无向完全图是欧拉图？为何值时为半欧拉图？（2）为何值时为欧拉图？ （3）为何值时为哈密整图？（3）为何值时，轮图为欧拉图？证：（1）一般情况下，不考虑无向图。因此因为各顶点的度均为，若使为欧拉图，必为偶数，因而必为奇数。即为奇数时，完全图是欧拉图。若或为奇数时，是半欧拉图。（2）当均为偶数时，为欧拉图。（3）当时，为哈密整图。（4）设为轮图，在
5、中，有个顶点的度为3，因而对于任意取值，轮图都不是欧拉图。例1 判断图5所示的图是否为哈密顿图，若是写出哈密顿回路，否则证明其不是哈密顿图。精品. (a) (b) 图3 图4 例2 给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点和，均有。例3 试求中不同的哈密顿回路的个数。例4 (1) 证明具有奇数顶点的偶图不是哈密顿图；用此结论证明图8所示的图不是哈密顿图。(2) 完全偶图为哈密顿图的充分必要条件是什么？证：(1) 设是一个具有奇数顶点的偶图，则的顶点集有一个二划分，即且有。 不妨设，则有。由哈密顿图的必要条件可知：不是哈密顿图。 题中所给的图中无奇数长的回路，因而此图是偶图。
6、而且此图中有13个顶点，因此它不是哈密顿图。(2) 若，有(1)可知不是哈密顿图；若，同理有不是哈密顿图。精品.故是哈密顿图时只有，即。若，则，由定理知：是哈密顿图。例5 菱形12面体的表面上有无哈密顿回路？例6设是连通图且顶点数为，最小度数为，则中有一长至少为的路。分析: 采用最长路法，设连通图的最长路为且。再看这条路的端点，端点只能与上的顶点相邻，这样就可以构成一个回路，对于回路外的顶点，因为仍与此回路上的某些顶点相邻，所以可以把这个顶点连到回路上，然后再打开回路，显然这时有一条路比假设时的路更长了，所以假设不成立。证：假设中的最长路为：，其长度为。因为， ，所以存在，使 与在中相邻，得一
7、长为的回路：。又因为连通，且的顶点数，故存在与回路上相邻，则把回路在处断开，并把连入回路中，得到一条长为的路，矛盾。所以中有一长至少为的路。例7 证明：彼德森()图不是哈密顿图。 例8 某工厂生产由6种不同颜色的纱织成的双色布。双色布中，每一种颜色至少和其他精品.3种颜色搭配。证明：可以挑出3种不同的双色布，它们含有所有6种颜色。证：用6个不同的点分别表示6种不同颜色的纱，两个点间联一条线当且仅当用这两点所表示的两种不同颜色的纱织成一种双色布。于是，我们得到一个有6个点的图G。由于每种颜色的纱至少和3种其他颜色的纱搭配，所以G的每个顶点的度至少是3。于是，由定理1，G有哈密顿回路。回路上有6条
8、边，对应了6种不同的双色布。间隔取出3条边，它们包含了全部6种颜色。与例8等价的例题：例9 今要将6个人分成3组（每组2个人）去完成3项任务，已知每个人至少与其余5个人中的3个人能相互合作，问：(1)能否使得每组2个人都能相互合作？(2)你能给出集中方案？（两种）例10 某公司来了9名新雇员，工作时间不能互相交谈。为了尽快互相了解，他们决定利用每天吃午饭时间相互交谈。于是，每天在吃午饭时他们围在一张圆桌旁坐下，他们是这样安排的，每一次每人的左、右邻均与以前的人不同。问这样的安排法能坚持多久？解：平面上9个互不相同的点分别代表9个新雇员。因为每个人都可以为其他每个人的左或右邻，所以用两点的联线表
9、示相应的两个人互为左右邻。于是得到了有9个顶点的完全图K9。于是，我们的问题中的一种坐法就是K9的一个哈密顿回路。由于每次的安排中，每人的左、右邻均与以前的人不同，所以我们的问题就是求K9中有多少个两两无公共边的哈密顿回路。由图1.6.5不难发现，K9中恰有4个两两无公共边的哈密顿回路。它们是：1234567891，1357924681，1473825961，1584936271。精品.于是，他们的这种安排法仅能维持4天。例10可推广为n个雇员的一般情况问题。这时，当n为奇数时，这种安排法仅能维持(n-1)/2天；当n为偶数时，这种安排法仅能维持(n-2)/2天。习题课3例2设，其中为正整数，
10、。若存在个顶点的简单图，使得顶点的度为，则称是可图解的。下面给出的各序列中哪些是可图解的？哪些不是，为什么？（1） （1，1，1，2，3）； （6） （1，3，3，3）； （2） （0，1，1，2，3，3）； （7） （2，3，3，4，5，6）； （3） （3，3，3，3）； （8） （1，3，3，4，5，6，6）； （4） （2，3，3，4，4，5）； （9） （2，2，4）； （5） （2，3，4，4，5）； （10） （1，2，2，3，4，5）。解：（1），（2），（3）全是可图解的，它们对应的图分别如图3中所示；其余的各序列都不是可图解的。在（4），（7），（10）中均有奇数个奇度顶点
11、，根据握手定理的推论，它们自然都不是可图解的。另外在阶简单图中，每个顶点的度至多为，因而（5）和（9）均不可图解。若（6）是可图解的，则设，因为的度都是3，因而要求与之间有边关联，但因的度为1，这是不可能的，所以（6）也是不可图解的。精品.在（8）中，因而每个顶点至多6度。若（8）是可图解的，设，因而均应与相邻，这也是不可能的，因而（8）也不可图解。 (a) (b) (c)图3例3 至少要删除多少条边，才能使不连通且其中有一个连通分支恰有个顶点？简述理由。 证：要使删除边后的图边数最多，则删除的边最少。满足有一个连通分支恰有个顶点的图的最大边数为： 则至少应该删除的边数为： 。例4若是一个恰有
12、两个奇度顶点和的无向图，则连通连通。证： 显然成立。 假设不连通，则有个分支：，由题意不在一个分支上，于是含有的顶点的分支只有一个奇度数顶点与握手定理的推论矛盾。于是假设不成立，即是连通的。例5设为阶简单无向图，且为奇数，和的补图中度数为奇数的顶点的个数是否一定相等？试证明你的结论。精品.解：一定相等。因为为奇数，则对于奇数个顶点的阶无向完全图，每个顶点的度数必为偶数。若的奇度数顶点为个，则对应补图在这个顶点的度数必为（偶数奇数）奇数。另外，对于中度数为偶数的顶点，其在补图中，这些顶点的度数仍为（偶数偶数）偶数。所以，中度数为奇数的顶点个数与中度数为奇数的顶点个数相同。例6证明：完全图中至少存
13、在彼此无公共边的两条哈密顿回路和一条哈密顿路？证：在中，由定理可知，必有一条哈密顿回路；令为中删除中全部边之后的图，则中每个顶点的度均为，故仍为哈密顿图，因而存在中的哈密顿回路，显然与无公共边。再设为中删除中的全部边后所得图，则每个顶点的度均为。又由定理可知为半哈密顿图，因而中存在哈密顿路。设为中的一条哈密顿路，显然无公共边。例7 已知7个人中，会讲英语；会讲英语和汉语；会讲英语、意大利语和俄语；会讲汉语和日语；会讲意大利语和德语；会讲俄语、日语和法语；会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？证：用7个顶点代表7个人，若两人能交谈（会讲同一种语言），就在代
14、表他们的顶点之间连一条无向边，所得无向图如图4所示，此图中存在哈密顿回路：（如图4粗边所示），于是按图4所示的顺序安排座位即可。精品. (a)(b) (c)图4例8将无向完全图的边随意地涂上红色或绿色，证明：无论何种涂法，总存在红色的或绿色的。证：设的顶点为。给的边任意用红、绿色涂上，由鸽巢原理可知，由引出的5条边中存在3条涂同种颜色的边。不妨设存在3条红色的边，又不妨设这3条边的另一个端点分别是（也可重新给顶点排序）。 若构成的中的边再有一条红色边。比如（）着的是红色，构成的三角形为红色的。若构成的的边全是绿色的边，则存在绿色边的。这就证明了我们的结论。例9已知9个人，其中和两个人握过手，各
15、和3个人握过手，和4个人握过手，各和5个人握过手，和6个人握过手。证明这9个人中一定可以找出3个人互相握过手。分析：以为顶点，握过手就连一条边，得到一个无向图。只要证明中有三角形子图，即可得一定有3个人互相握过手。 证：设为图的9个顶点，握过手就连一条边，于是得精品.到图。根据题意有：，。与相邻的点有6个，其中必有一点为之一，因此有。与相邻的其余5个点中必存在一点与相邻如图4所示，否则有，矛盾。由此三个人互相握过手。 图5 图6 图7例10如图6所示的图是哈密顿图。试证明：若图中的哈密顿回路中含边，则它一定同时也含。证：设为图中一条哈密顿回路，在中，假设不在中，要推出矛盾。图中除外，与关联的边
16、各有两条，而只能各有一条边在中，由对称性设在中（不可能或同时在中）。这就相当于在图7中所示的图中求一条哈密顿回路，而此时，均为图中割点，这是不可能的，因而必在中。例11某次会议有20人参加，其中每个人都至少有10个朋友，这20人围一圆桌入席，要想使与每个人相邻的两位都是朋友是否可能？根据什么？证：可能。依题意，若用顶点代表人，两人是朋友时相应顶点间连一条边，则得到一个无向图，该题转化为求哈密顿回路问题。由于对任意精品.,有，因而。 又定理可知，为哈密顿图，中存在哈密顿回路，按此回路各点位置入席即为所求。例12 设是一个个顶点的连通图。和是的两个不邻接的顶点,并且。证明：是哈密顿图是哈密顿图。证
17、明： 显然成立。 假设不是哈密顿图，则由题意知，在中必有一条从到的哈密顿路。不妨设此路为，令，则在中与邻接的顶点为，其中。此时顶点不能与顶点邻接。否则有哈密顿回路，因此至少与中的个顶点不邻接。于是，从而，即，与题设矛盾。故假设不成立，因此是哈密顿图。例13设为阶无向简单图，已知，证明中存在长度为偶数的回路。证：对无向简单图的顶点个数进行数学归纳证明：当时，为完全图，结论显然成立，所得的回路的长度为4。设当时结论成立，长度为偶数的回路为。则当时，长度为偶数的回路也在顶点数为的图中，则结论成立。例14设是个顶点的简单无向图，设中最长的路的长度为，起点与终点分别为,，而且。证明：中必有与不完全相同但
18、长度也为的路。精品.证：设图的最长的路为：，其长度为。因为最长的路，所以与,相邻的顶点必在上。若和相邻，则构成一个回路，回路长为；若和不相邻，设与相邻的顶点为，其中，则必与某个邻接。否则，至多与最长路上其余的顶点邻接，所以这是不可能的。于是是中的一个回路，此回路长度为。去掉这个回路的任意一条边，便得到一条相应的最长的路，所以对于这个回路有个不同的最长的路且。故中必有与不完全相同，但长度也为的路。例15 一个一维立方体是这样的无向图：顶点集为长为的所有字符串之集，两个顶点邻接当且仅当相应的两个字符串仅有一个相应位不同，其他各位均相同。则（1）有多少个顶点? （2）证明是正则图； （3）证明是偶图；（4）证明是条边；（5）是否为哈密顿图？解：（1）有个顶点。（2）按中边的定义知：每个顶点的度为，所以是正则图；精品.（3）根据中边的定义知：每条边的两个端点名中的个数的奇偶性不同，于是，顶点名为偶数个的那些顶点互相之间无边，其余顶点间也无边。所以，为偶图。（4）由（1）和（2）知：，故边数（5）的图解如图3所示。是哈密顿图，例如000，010，011，001，101，111，110，100，000为一个哈密顿回路。图3 立方体如有侵权请联系告知删除，感谢你们的配合！精品