《篇图论习题》PPT课件

《《篇图论习题》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论部分第五章图的基本概念习题课1例1设d=(d1,d2,…,dn),其中di为非负整数，i=1,2,…,n。若存在n个顶点的(简单)无向图,使得顶点vi的度为di，则称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

2、）。例2画出具有6、8、10、…、2n个顶点的三次图；是否有7个顶点的三次图？例3无向图有21条边，12个3度数顶点，其余顶点的度数均为2，求的顶点数。(p=15)例4下列各无向图中有几个顶点？(1)16条边，每个顶点的度为2；(2)21条边，3个4度顶点，其余的都为3度数顶点；(3)24条边，各顶点的度数相同。(1.p=16;2.p=13;3.pk=48讨论)例5设图G中有9个顶点，每个顶点的度不是5就是6。证明:G中至少有5个6度顶点或至少有6个5度顶点。例6有n个药箱，若每两个药箱里有一种相同的药，而每种药恰好放在两个药箱中，问药

3、箱里共有多少种药？例7设G是有个p顶点，q条边的无向图，各顶点的度数均为3。则(1)若q=3p-6,证明:G在同构意义下唯一，并求p,q。(2)若p=6，证明:G在同构的意义下不唯一。例8已知p阶(简单)无向图中有q条边，各顶点的度数均为3，又2p=q+3，试画出满足条件的所有不同构的G。例99个学生，每个学生向其他学生中的3个学生各送一张贺年卡。确定能否使每个学生收到的卡均来自其送过卡的相同人？为什么？解:否，不存在9（奇数）个顶点的3－正则图。习题课2例10若G是一个恰有两个奇度顶点u和v的无向图，则（1）顶点u与v连通；（2）G连

4、通G+uv连通。例1设G为p阶简单无向图，p＞2且p为奇数，G和G的补图GC中度数为奇数的顶点的个数是否一定相等？试证明你的结论。例2设V={v1,v2,…,vp}，计算以V为顶点集的无向图的个数是多少？(KP有多少个生成子图)例3设V={v1,v2,…,vp},q≤p(p-1)/2，计算以V为顶点集具有q条边的无向图的个数是多少？例4设G是（p,q）图，r≤q，则具有r条边的G的生成子图有多少？答案：2p(p-1)/2，Cqp(p-1)/2，Crq。例5证明：若无向图G是不连通的，则G的补图GC是连通的。（逆命题不成立）例6将无向完

5、全图K6的边随意地涂上红色或绿色,证明:无论何种涂法,总有红色的K3或绿色K3。例7给无向完全图Kp(p≥7)的各边随意地涂上红色或绿色，若已知从某点v0引出的p-1条边中至少有6条边涂红色，则Kp存在红色的K4或绿色的K3。例8有17位学者，每2位讨论3篇论文中的一篇且仅一篇，证明：至少有3位学者，他们相互讨论的是同一篇论文。习题3例1设p，q为正整数，则（1）p为何值时，无向完全图Kp是欧拉图？p为何值时Kp为半欧拉图？（2）p,q为何值时Kp,q为欧拉图？（3）p,q为何值时Kp,q为哈密顿图？（4）p为何值时，轮图Wp为欧拉图？

6、例2判断如图所示的图是否为哈密顿图，若是写出哈密顿圈，否则证明其不是哈密顿图。例3给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有degu+degv≥9。例4证明：完全图K9中至少存在彼此无公共边的两条哈密顿回路和一条哈密顿路？例5试求Kp中不同的哈密顿圈的个数。例6(1)证明具有奇数顶点的偶图不是哈密顿图；用此结论证明如图所示的图不是哈密顿图。(2)完全偶图Km,n为哈密顿图的充要条件是什么？例7菱形12面体的表面上有无哈密顿回路？例8设G=(V,E)是连通图且顶点数为p,最小度数为δ，若p>2δ,则G中有一长

7、至少为2δ的路。例9证明：彼德森图不是哈密顿图。例10某工厂生产由6种不同颜色的纱织成的双色布。双色布中，每一种颜色至少和其他3种颜色搭配。证明:可以挑出3种不同的双色布,它们含有所有6种颜色。与例8等价的例题：例11今要将6个人分成3组（每组2个人）去完成3项任务，已知每个人至少与其余5个人中的3个人能相互合作，问：(1)能否使得每组2个人都能相互合作？(2)你能给出集中方案？（两种）例12设G=(V,E)是p(p>3)个顶点的简单无向图,设G中最长路L的长度为l(l≥2)，起点与终点分别为u,v，而且degu+degv≥p。证明：G

8、中必有与L不完全相同但长度也为L的路。ⅰ例13某公司来了9名新雇员，工作时间不能互相交谈。为了尽快互相了解，他们决定利用每天吃午饭时间相互交谈。于是，每天在吃午饭时他们围在一张圆桌旁坐下，他们是这样安排的，