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

1第五章图的基本概念习题课11.画出具有6、8、10、…、2n个顶点的三次图；是否有7个顶点的三次图？2.无向图G有21条边，12个3度数顶点，其余顶点的度数均为2，求G的顶点数p。解：设图的顶点为p，根据握手定理：1deg()2piivq，有212)12(2312p，得15302pp，。3.下列各无向图中有几个顶点？（1）16条边，每个顶点的度为2；（2）21条边，3个4度顶点，其余的都为3度数顶点；（3）24条边，各顶点的度数相同。解：设图的顶点为p，根据握手定理：（1）1deg()2piivq，即2221632pq；所以16p，即有16个顶点。（2）1deg()2piivq，即433(3)222142pq，所以13p。（3）各点的度数为k，则1deg()2ipivq，即222448kpq，于是①若1k，48p；②若2k，24p；③若3k，16p；④若4k，12p；⑤若6k，8p；⑥若8k，16p；⑦若12k，4p；⑧若16k，3p；2⑨若24k，2p；⑩若48k，1p。4．设图G中9个顶点，每个顶点的度不是5就是6。证明G中至少有5个6度顶点或至少有6个5度顶点。证：由握手定理的推论可知，G中5度顶点数只能是0，2，6，8五种情况，此时6度顶点数分别为9，7，5，3，1个。以上五种情况都满足至少5个6度顶点或至少6个5度顶点的情况。5．有n个药箱，若每两个药箱里有一种相同的药，而每种药恰好放在两个药箱中，问药箱里共有多少种药？[就是求一个完全图nK的边数(1)(2)/2qpp]6.设G是有p个顶点，q条边的无向图，各顶点的度数均为3。则（1）若36qp，证明G同构意义下唯一，并求,pq；（2）若6p，证明G在同构的意义下不唯一。分析：在图论中，对于简单无向图和简单有向图，若涉及到边q与顶点p的问题，握手定理是十分有用的。解：（1）由于各顶点的度数均为3，现在有p个顶点，q条边，所以由握手定理知：1deg()2ipivq，即33nq，故2/3nm；又3632/3626qpqq，故6q，则2/364p。即4q，4p，此时所得的无向图如图1所示，该图是4个顶点的简单无向图中边最多的图，即为无向完全图4K。对于4个顶点的完全图，在同构意义下，4个顶点的完全图是唯一的。（2）若6p，由握手定理：1deg()2ipivq，即362q。故9q，此时有6,9pq，且每个顶点的度数为3；此时对于简单无向图，6个顶点，9条边及每个度数为3的有如图2所示两个非同构的图；()a与()b是非同构的图，所以6,9pq，度数为3的无向图G在同构的意义下是不唯一的。3（a）(b)图1图27.已知p阶简单图G中有q条边，各顶点的度数均为3，又23qp，试画出满足条件的所有不同构的G。解：由握手定理：1deg()32ipivpq，又23pq，即23qp。故322(23)46pqpp，即6p，239qp。此时有6p，9q且每个顶点的度数都为3，则不同构的无向图有两个，如图3所示。图38．9个学生，每个学生向其他学生中的3个学生各送一张贺年卡。确定能否使每个学生收到的卡均来自其送过卡的相同人？为什么？解：否，因为不存在9（奇数）个顶点的3－正则图习题课2例3设,pq为正整数，则（1）p为何值时，无向完全图pK是欧拉图？p为何值时pK为半欧拉图？（2）,pq为何值时,pqK为欧拉图？（3）,pq为何值时,pqK为哈密整图？4（3）p为何值时，轮图pW为欧拉图？证：（1）一般情况下，不考虑无向图1K。因此因为pK各顶点的度均为1p，若使pK为欧拉图，1p必为偶数，因而p必为奇数。即(3)pp为奇数时，完全图pK是欧拉图。若2p或(3)pp为奇数时，pK是半欧拉图。（2）当,2pq均为偶数时，,pqK为欧拉图。（3）当pq时，,pqK为哈密整图。（4）设(4)pWp为轮图，在pW中，有1p个顶点的度为3，因而对于任意取值(4)pp，轮图pW都不是欧拉图。例1判断图5所示的图是否为哈密顿图，若是写出哈密顿回路，否则证明其不是哈密顿图。ihjgfedcbajihgfedcba(a)(b)图3图4例2给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有degdeg9uv。例3试求pK中不同的哈密顿回路的个数。例4(1)证明具有奇数顶点的偶图不是哈密顿图；用此结论证明图8所示的图不是哈密顿图。5(2)完全偶图,mnK为哈密顿图的充分必要条件是什么？证：(1)设G是一个具有奇数顶点的偶图，则G的顶点集V有一个二划分，即22{,}VVV且有12||||VV。不妨设12||||VV，则有121()||||WGVVV。由哈密顿图的必要条件可知：G不是哈密顿图。题中所给的图中无奇数长的回路，因而此图是偶图。而且此图中有13个顶点，因此它不是哈密顿图。(2)若12||||VV，有(1)可知,mnK不是哈密顿图；若12||||VV，同理有,mnK不是哈密顿图。故,mnK是哈密顿图时只有12||||VV，即mn。若mn，则,,||/2||/2||uvVdegudegvVVV，由定理知：,mnK是哈密顿图。例5菱形12面体的表面上有无哈密顿回路？例6设(,)GVE是连通图且顶点数为p，最小度数为2p，则G中有一长至少为2的路。分析:采用最长路法，设连通图的最长路为L且||2L。再看这条路的端点，端点只能与L上的顶点相邻，这样就可以构成一个回路，对于回路外的顶点，因为仍与此回路上的某些顶点相邻，所以可以把这个顶点连到回路上，然后再打开回路，显然这时有一条路比假设时的路更长了，所以假设不成立。证：假设G中的最长路为L：01lLvvv，其长度为2l。因为0degv，1degv，所以存在01il，使01ivv与1ivv在G中相邻，得一长为1l的回路：0111110iivvvvvvv。又因为G连通，且G的顶点数2p，故存在(0)ivvil与回路上6(0)jvjl相邻，则把回路在jv处断开，并把v连入回路中，得到一条长为1l的路，矛盾。所以G中有一长至少为2的路。例7证明：彼德森(Petersen)图不是哈密顿图。例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个两两无公共边的哈密顿回路。它们是：1234567891，1357924681，1473825961，1584936271。于是，他们的这种安排法仅能维持4天。7例10可推广为n个雇员的一般情况问题。这时，当n为奇数时，这种安排法仅能维持(n-1)/2天；当n为偶数时，这种安排法仅能维持(n-2)/2天。习题课3例2设d12(,,,)nddd，其中id为正整数，1,2,,in。若存在n个顶点的简单图，使得顶点iv的度为id，则称d是可图解的。下面给出的各序列中哪些是可图解的？哪些不是，为什么？（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中(),(),()abc所示；其余的各序列都不是可图解的。在（4），（7），（10）中均有奇数个奇度顶点，根据握手定理的推论，它们自然都不是可图解的。另外在p阶简单图中，每个顶点的度至多为1p，因而（5）和（9）均不可图解。若（6）是可图解的，则设1234deg1,degdegdeg3vvvv，因为234,,vvv的度都是3，因而要求1v与234,,vvv之间有边关联，但因1v的度为1，这是不可能的，所以（6）也是不可图解的。在（8）中，7n，因而每个顶点至多6度。若（8）是可图解的，设1deg1v，67degdeg6vv，因而67,vv均应与1v相邻，这也是不可能的，因而（8）也不可图解。8(a)(b)(c)图3例3至少要删除多少条边，才能使(2)pKp不连通且其中有一个连通分支恰有k个顶点(0)kp？简述理由。证：要使删除边后的图边数最多，则删除的边最少。满足有一个连通分支恰有k个顶点的图的最大边数为：(1)()(1)22kknknk则至少应该删除的边数为：(1)(1)()(1)222nnkknknk。例4若G是一个恰有两个奇度顶点u和v的无向图，则G连通Guv连通。证：显然成立。假设G不连通，则G有(2)kk个分支：12,,,kGGG，由题意uv与不在一个分支上，于是含有uv或的顶点的分支只有一个奇度数顶点与握手定理的推论矛盾。于是假设不成立，即G是连通的。例5设G为p阶简单无向图，2p且p为奇数，G和G的补图cG中度数为奇数的顶点的个数是否一定相等？试证明你的结论。解：一定相等。因为2p为奇数，则对于奇数个顶点的p阶无向完全图，每个顶点的度数必为偶数。若G的奇度数顶点为1p个，则对应补图cG在这1p个顶点的度数必为（偶数－奇数）＝奇数。另外，对于G中度数为偶数的顶点，其在补图cG中，9这些顶点的度数仍为（偶数－偶数）＝偶数。所以，G中度数为奇数的顶点个数与cG中度数为奇数的顶点个数相同。例6证明：完全图9K中至少存在彼此无公共边的两条哈密顿回路和一条哈密顿路？证：在9K中，,deg8/2vVvp，由定理可知，必有一条哈密顿回路1C；令1G为9K中删除1C中全部边之后的图，则1G中每个顶点的度均为deg6/2vp，故1G仍为哈密顿图，因而存在1G中的哈密顿回路2C，显然1C与2C无公共边。再设2G为1G中删除2C中的全部边后所得图，则2G每个顶点的度均为deg4v。又由定理可知2G为半哈密顿图，因而2G中存在哈密顿路。设L为2G中的一条哈密顿路，显然12,,CCL无公共边。例7已知,,,,,,abcdefg7个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？证：