第二篇--图论习题

习题课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画出具有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个药箱，若每两个药箱里有一种相同的药，而每种药恰好放在两个药箱中，问药箱里共有多少种药？例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连通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将无向完全图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为欧拉图？例2判断如图所示的图是否为哈密顿图，若是写出哈密顿圈，否则证明其不是哈密顿图。abcdefgjhiabcdefghij例3给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有degu+degv≥9。例4证明：完全图K9中至少存在彼此无公共边的两条哈密顿回路和一条哈密顿路？例5试求Kp中不同的哈密顿圈的个数。例6(1)证明具有奇数顶点的偶图不是哈密顿图；用此结论证明如图所示的图不是哈密顿图。(2)完全偶图Km,n为哈密顿图的充要条件是什么？例7菱形12面体的表面上有无哈密顿回路？例8设G=(V,E)是连通图且顶点数为p,最小度数为δ，若p2δ,则G中有一长至少为2δ的路。例9证明：彼德森图不是哈密顿图。例10某工厂生产由6种不同颜色的纱织成的双色布。双色布中，每一种颜色至少和其他3种颜色搭配。证明:可以挑出3种不同的双色布,它们含有所有6种颜色。与例8等价的例题：例11今要将6个人分成3组（每组2个人）去完成3项任务，已知每个人至少与其余5个人中的3个人能相互合作，问：(1)能否使得每组2个人都能相互合作？(2)你能给出集中方案？（两种）例12设G=(V,E)是p(p3)个顶点的简单无向图,设G中最长路L的长度为l(l≥2)，起点与终点分别为u,v，而且degu+degv≥p。证明：G中必有与L不完全相同但长度也为L的路。ⅰ例13某公司来了9名新雇员，工作时间不能互相交谈。为了尽快互相了解，他们决定利用每天吃午饭时间相互交谈。于是，每天在吃午饭时他们围在一张圆桌旁坐下，他们是这样安排的，每一次每人的左、右邻均与以前的人不同。问这样的安排法能坚持多久？例14已知a,b,c,d,e,f,g7个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？例15设G为p个顶点的简单无向图。(1)若G的边数q=(p-1)·(p-2)/2+2，证明G为哈密顿图。(2)若G的边数q=(p-1)·(p-2)/2+1，则G是否一定为哈密顿图？例16如图所示的图G是哈密顿图。试证明：若图中的哈密顿回路中含边e1，则它一定同时也含e2。例17已知9个人v1,v2,…,v9，其中v1和两个人握过手，v2,v3,v4,v5各和3个人握过手，v6和4个人握过手，v7,v8各和5个人握过手，v9和6个人握过手。证明:这9个人中一定可以找出3个人互相握过手。例18某次会议有20人参加，其中每个人都至少有10个朋友，这20人围一圆桌入席，要想使与每个人相邻的两位都是朋友是否可能？根据什么？例19设G是一个有p(p≥3)个顶点的连通图。u和v是G的两个不邻接的顶点,并且degu+degv≥p。证明：G是哈密顿图G+uv是哈密顿图。第六章树和割集(习题课1)例1若无向图G中有个p顶点，p-1条边，则G为树。这个命题正确吗？为什么？例2画出具有4、5、6、7个顶点的所有非同构的无向树。例3设无向图G是由K(K≥2)棵树构成的森林，至少在G中添加多少条边才能使G成为一棵树？例4设T是一棵树，T有3个度为3顶点，1个2度顶点，其余均是1度顶点。则(1)求T有几个1度顶点？(2)画出满足上述要求的不同构的两棵树。例5设树T中有2n个度为1的顶点，有3n个度为2的顶点，有n个度为3的顶点，则这棵树T有多少个顶点和多少条边？例6设T是一棵树且△(T)≥k，证明:T中至少有k个度为1的顶点。例7证明:恰有两个顶点度数为1的树必为一条通路。例8(1)一棵无向树有ni个度数为i的顶点,i=1,2,…,k。n2,n3,….nk均为已知数，问n1应为多少？(2)在(1)中，若nr(3≤r≤k)未知，nj(j≠r)均为已知数，问nr应为多少？例9设无向图G中有p个顶点，q-1条边，则G为连通图当且仅当G中无回路。例10设G是一个(p,q)图,证明:若q≥p,则G中必有圈。例11设d1,d2,…,dp是p个正整数,p≥2,且。证明:存在一棵顶点度数为d1,d2,…,dp的树。例12证明:任一非平凡树最长路的两个端点都是树叶。122piidp例1设图G中有9个顶点，每个顶点的度不是5就是6。证明:G中至少有5个6度顶点或至少有6个5度顶点。例2设G是有个p顶点，q条边的无向图，各顶点的度数均为3。则(1)若q=3p-6,证明:G在同构意义下唯一，并求p,q。(2)若p=6，证明:G在同构的意义下不唯一。例3已知p阶(简单)无向图中有q条边，各顶点的度数均为3，又2p=q+3，试画出满足条件的所有不同构的G。习题课２例１设G是连通图，满足下面条件之一的边应具有什么性质？（1）在G的任何生成树中；（2）不在G的任何生成树中。例2非平凡无向连通图G是树当且仅当G的的每条边都是桥。例3设T是一棵树，p≥2，则（1）p个顶点的树至多有多少个割点；（2）p个顶点的树有多少个桥？例4证明或否定断言：连通图G的任意边是G的某一棵生成树的弦。例5设T是连通图G中的一棵生成树，证明：T的补中不含中任何割集。[T的补就是T的弦]TGT第七章习题课１定理1设G=(V1∪V2，E)是一个偶图，|V1|≤|V2|。G中存在从V1到V2的完全匹配⇔是V1中任意k个顶点(k=1,2,…,|V1|)至少与V2中的k个顶点相连接。例１现有4名教师：张、王、李、赵，要求他们去教4门课程：数学、物理、电工和计算机科学。已知张能教数学和计算机科学；王能教物理和电工；李能教数学、物理和电工；赵只能教电工。如何安排才能使4位教师都能教课，并且每门课都有人教？共有几种方案？用相异性条件判断一个偶图是否存在完全匹配常常很不方便，下面的充分条件比较便于实际应用。定理2设G=(V1∪V2，E)是一个偶图，|V1|≤|V2|。G中存在从V1到V2的完全匹配的充分条件是存在正整数t，使得V1中每个顶点的度大于等于t，V2中每个顶点的度小于等于t。该条件称为t条件。例２某年级共开设7门课程，由7位教师承担。已知每位教师都能担任其中的3门课程。他们将自己能担任的课程报到教务处后，教务处人员发现每门课都恰好有3位教师能担任。问教务处人员能否安排这7位教师每人担任1门课，并且每门课都有人承担。定理3从t条件可以推出相异性条件。注意：定理3中反过来不能推出t条件。推论1任何r-正则偶图G＝(V1∪V2,E)必有一个完美匹配，其中r≥1。第七章平面图和图的着色习题课１1.设G是有k个分支、f个面的(p,q)平面图，则p-q+f=k+1。2.证明：下列4个图均是可平面图。3．如图所示的图G是否为平面图？是否为极大平面图？为什么？4.证明：极大平面图G一定是连通图。5.设G是有p(p≥3)个顶点的简单平面连通图，且G的每个面均是由3条边围成，证明：G是极大平面图。（若G是极大平面图，则G的每个面都是三角形）6.由6个顶点，12条边构成的平面连通图G中，每个面由几条边围成？为什么？7．证明：若每个顶点的度数大于等于3时，则不存在有7条边的平面连通图。(等价命题：证明：不存在7条棱的凸多面体)8.设G是顶点p≥11的平面图，证明：G的补图Gc是非平面图。(设G是顶点p≥11的图，证明：G与G的补图Gc至少有一个是非平面图。)9.设G是平面连通图，顶点为p面数f，证明:(1)若p≥3，则f≤2p-4。(2)若δ(G)=4,则G中至少有6个顶点的度数≤5。10．设G是边数q30的平面图,证明:G中存在顶点v，使得degv≤4。习题课21.说明图中所示图(1)(2)是否是非平面图？2．证明:彼得森图不是平面图。(1)收缩法；(2)欧拉公式法；(3)收缩到K3,3。3.设G是无向图,p8,则G与Gc中至少有一个是平面图。4.设平面图G的顶点数p=7,边数q=15，证明G是连通的。习题课31．判断下面命题是否正确，并说明理由。任意平面图G的对偶图G*的对偶图G**与G同构。2.设G*是平面图G的对偶图，证明：p*=f，q*=q，f*=p-k+1。其中k(k≥1)为G的连通分支数。3.证明：若G是自对偶的平面图，则q=2p-2。其中p和q是G的边与顶点数。4．把平面分成p个区域，每两个区域都相邻，问p最大为多少？5.证明：不存在具有5个面，每两个面都共享一条公共边的平面图G。习题课41．求下列各类图顶点的色数。(1)p阶零图Np;(2)完全图Kp;(3)p阶轮图Wp(轮图至少有4个顶点);(4)彼德森图(如图1所示);(5)如图2所示。2.若图G的色数（或顶点色数）K(G)=k，则G中至少有k(k-1)/2条边。3.设G是一个没有三角形的平面图，则（1）证明：G中存在一个顶点v，使得degv≤3；（2）证明：G是4-可着色的。4.5四色问题在图论