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

精选优质文档-----倾情为你奉上第五章 图的基本概念习 题 课 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个顶点，每个顶点的度不是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，现在有个顶点，条边，所以由握手定理知：，即，故；又，故，则即，，此时所得的无向图如图1所示，该图是4个顶点的简单无向图中边最多的图，即为无向完全图对于4个顶点的完全图，在同构意义下，4个顶点的完全图是唯一的2）若，由握手定理：，即故，此时有，且每个顶点的度数为3；此时对于简单无向图，6个顶点，9条边及每个度数为3的有如图2所示两个非同构的图；与是非同构的图，所以，度数为3的无向图在同构的意义下是不唯一的 （a） (b)图1 图27.已知阶简单图中有条边，各顶点的度数均为3，又，试画出满足条件的所有不同构的解：由握手定理：，又，即故，即，此时有，且每个顶点的度数都为3，则不同构的无向图有两个，如图3所示。

图3 8．9个学生，每个学生向其他学生中的3个学生各送一张贺年卡确定能否使每个学生收到的卡均来自其送过卡的相同人？为什么？解：否，因为不存在9（奇数）个顶点的3－正则图习题课2例3设为正整数，则（1）为何值时，无向完全图是欧拉图？为何值时为半欧拉图？（2）为何值时为欧拉图？ （3）为何值时为哈密整图？（3）为何值时，轮图为欧拉图？证：（1）一般情况下，不考虑无向图因此因为各顶点的度均为，若使为欧拉图，必为偶数，因而必为奇数即为奇数时，完全图是欧拉图若或为奇数时，是半欧拉图2）当均为偶数时，为欧拉图3）当时，为哈密整图4）设为轮图，在中，有个顶点的度为3，因而对于任意取值，轮图都不是欧拉图例1 判断图5所示的图是否为哈密顿图，若是写出哈密顿回路，否则证明其不是哈密顿图 (a) (b) 图3 图4 例2 给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点和，均有。

例3 试求中不同的哈密顿回路的个数例4 (1) 证明具有奇数顶点的偶图不是哈密顿图；用此结论证明图8所示的图不是哈密顿图2) 完全偶图为哈密顿图的充分必要条件是什么？证：(1) 设是一个具有奇数顶点的偶图，则的顶点集有一个二划分，即且有 不妨设，则有由哈密顿图的必要条件可知：不是哈密顿图 题中所给的图中无奇数长的回路，因而此图是偶图而且此图中有13个顶点，因此它不是哈密顿图2) 若，有(1)可知不是哈密顿图；若，同理有不是哈密顿图故是哈密顿图时只有，即若，则，由定理知：是哈密顿图例5 菱形12面体的表面上有无哈密顿回路？例6设是连通图且顶点数为，最小度数为，则中有一长至少为的路分析: 采用最长路法，设连通图的最长路为且再看这条路的端点，端点只能与上的顶点相邻，这样就可以构成一个回路，对于回路外的顶点，因为仍与此回路上的某些顶点相邻，所以可以把这个顶点连到回路上，然后再打开回路，显然这时有一条路比假设时的路更长了，所以假设不成立证：假设中的最长路为：，其长度为因为， ，所以存在，使 与在中相邻，得一长为的回路：又因为连通，且的顶点数，故存在与回路上相邻，则把回路在处断开，并把连入回路中，得到一条长为的路，矛盾。

所以中有一长至少为的路例7 证明：彼德森()图不是哈密顿图 例8 某工厂生产由6种不同颜色的纱织成的双色布双色布中，每一种颜色至少和其他3种颜色搭配证明：可以挑出3种不同的双色布，它们含有所有6种颜色证：用6个不同的点分别表示6种不同颜色的纱，两个点间联一条线当且仅当用这两点所表示的两种不同颜色的纱织成一种双色布于是，我们得到一个有6个点的图G由于每种颜色的纱至少和3种其他颜色的纱搭配，所以G的每个顶点的度至少是3于是，由定理1，G有哈密顿回路回路上有6条边，对应了6种不同的双色布间隔取出3条边，它们包含了全部6种颜色与例8等价的例题：例9 今要将6个人分成3组（每组2个人）去完成3项任务，已知每个人至少与其余5个人中的3个人能相互合作，问：(1)能否使得每组2个人都能相互合作？(2)你能给出集中方案？（两种）例10 某公司来了9名新雇员，工作时间不能互相交谈为了尽快互相了解，他们决定利用每天吃午饭时间相互交谈于是，每天在吃午饭时他们围在一张圆桌旁坐下，他们是这样安排的，每一次每人的左、右邻均与以前的人不同问这样的安排法能坚持多久？解：平面上9个互不相同的点分别代表9个新雇员因为每个人都可以为其他每个人的左或右邻，所以用两点的联线表示相应的两个人互为左右邻。

于是得到了有9个顶点的完全图K9于是，我们的问题中的一种坐法就是K9的一个哈密顿回路由于每次的安排中，每人的左、右邻均与以前的人不同，所以我们的问题就是求K9中有多少个两两无公共边的哈密顿回路由图1.6.5不难发现，K9中恰有4个两两无公共边的哈密顿回路它们是：，，，于是，他们的这种安排法仅能维持4天例10可推广为n个雇员的一般情况问题这时，当n为奇数时，这种安排法仅能维持(n-1)/2天；当n为偶数时，这种安排法仅能维持(n-2)/2天习题课3例2设，其中为正整数，若存在个顶点的简单图，使得顶点的度为，则称是可图解的下面给出的各序列中哪些是可图解的？哪些不是，为什么？（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）中均有奇数个奇度顶点，根据握手定理的推论，它们自然都不是可图解的另外在阶简单图中，每个顶点的度至多为，因而（5）和（9）均不可图解若（6）是可图解的，则设，因为的度都是3，因而要求与之间有边关联，但因的度为1，这是不可能的，所以（6）也是不可图解的在（8）中，，因而每个顶点至多6度若（8）是可图解的，设，，因而均应与相邻，这也是不可能的，因而（8）也不可图解 (a) (b) (c)图3例3 至少要删除多少条边，才能使不连通且其中有一个连通分支恰有个顶点？简述理由 证：要使删除边后的图边数最多，则删除的边最少满足有一个连通分支恰有个顶点的图的最大边数为： 则至少应该删除的边数为： 例4若是一个恰有两个奇度顶点和的无向图，则连通连通证： 显然成立 假设不连通，则有个分支：，由题意不在一个分支上，于是含有的顶点的分支只有一个奇度数顶点与握手定理的推论矛盾于是假设不成立，即是连通的例5设为阶简单无向图，且为奇数，和的补图中度数为奇数的顶点的个数是否一定相等？试证明你的结论。

解：一定相等因为为奇数，则对于奇数个顶点的阶无向完全图，每个顶点的度数必为偶数若的奇度数顶点为个，则对应补图在这个顶点的度数必为（偶数－奇数）＝奇数另外，对于中度数为偶数的顶点，其在补图中，这些顶点的度数仍为（偶数－偶数）＝偶数所以，中度数为奇数的顶点个数与中度数为奇数的顶点个数相同例6证明：完全图中至少存在彼此无公共边的两条哈密顿回路和一条哈密顿路？证：在中，，由定理可知，必有一条哈密顿回路；令为中删除中全部边之后的图，则中每个顶点的度均为，故仍为哈密顿图，因而存在中的哈密顿回路，显然与无公共边再设为中删除中的全部边后所得图，则每个顶点的度均为又由定理可知为半哈密顿图，因而中存在哈密顿路设为中的一条哈密顿路，显然无公共边例7 已知7个人中，会讲英语；会讲英语和汉语；会讲英语、意大利语和俄语；会讲汉语和日语；会讲意大利语和德语；会讲俄语、日语和法语；会讲德语和法语能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？证：用7个顶点代表7个人，若两人能交谈（会讲同一种语言），就在代表他们的顶点之间连一条无向边，所得无向图如图4所示，此图中存在哈密顿回路：（如图4粗边所示），于是按图4所示的顺序安排座位即可。

(a) (b) (c)图4例8将无向完全图的边随意地涂上红色或绿色，证明：无论何种涂法，总存在红色的或绿色的证：设的顶点为给的边任意用红、绿色涂上，由鸽巢原理可知，由引出的5条边中存在3条涂同种颜色的边不妨设存在3条红色的边，又不妨设这3条边的另一个端点分别是（也可重新给顶点排序） 若构成的中的边再有一条红色边比如（）着的是红色，构成的三角形为红色的若构成的的边全是绿色的边，则存在绿色边的这就证明了我们的结论例9已知9个人，其中和两个人握过手，各和3个人握过手，和4个人握过手，各和5个人握过手，和6个人握过手证明这9个人中一定可以找出3个人互相握过手分析：以为顶点，握过手就连一条边，得到一个无向图只要证明中有三角形子图，即可得一定有3个人互相握过手 证：设为图的9个顶点，握过手就连一条边，于是得到图。