第二篇-图论习题课件.ppt

1、习题课习题课1 1例例1 1 设设d=(d1,d2,d=(d1,d2,dn),dn),其中其中didi为非负整数，为非负整数，i=1,2,i=1,2,n,n。若存在。若存在n n个顶点的个顶点的( (简单简单) )无向图无向图, ,使得顶使得顶点点vivi的度为的度为didi，则称，则称d d是可图解的。下面给出的各序列是可图解的。下面给出的各序列中哪些是可图解的？哪些不是，为什么？中哪些是可图解的？哪些不是，为什么？（1 1）（）（1,1,1,2,31,1,1,2,3）；）； （6 6）（）（1,3,3,31,3,3,3）；）；（2 2）（）（0,1,1,2,3,30,1,1,2,3,3）；

2、（）；（7 7）（）（2,3,3,4,5,62,3,3,4,5,6）；）；（3 3）（）（3,3,3,33,3,3,3）；）； （8 8）（）（1,3,3,4,5,6,61,3,3,4,5,6,6）；）；（4 4）（）（2,3,3,4,4,52,3,3,4,4,5）；（）；（9 9）（）（2,2,42,2,4）；）；（5 5）（）（2,3,4,4,52,3,4,4,5）；）； （1010）(1,2,2,3,4,5(1,2,2,3,4,5）。）。例例2 2 画出具有画出具有 6 6、8 8、1010、2n2n个顶点的三次图；个顶点的三次图； 是否有是否有7 7个顶点的三次图？个顶点的三次图？例例

3、3 3 无向图有无向图有2121条边，条边，1212个个3 3度数顶点，其余顶点的度数顶点，其余顶点的度数均为度数均为2 2，求的顶点数。，求的顶点数。 (p=15)(p=15) 例例4 4 下列各无向图中有几个顶点？下列各无向图中有几个顶点？ (1) 16(1) 16条边，每个顶点的度为条边，每个顶点的度为2 2； (2) 21(2) 21条边，条边，3 3个个4 4度顶点，其余的都为度顶点，其余的都为3 3度数顶点；度数顶点； (3) 24(3) 24条边，各顶点的度数相同。条边，各顶点的度数相同。 (1. p=16; 2. p=13; 3. pk=48(1. p=16; 2. p=13;

4、 3. pk=48讨论讨论) )例例5 5 设图设图G G中有中有9 9个顶点，每个顶点的度不是个顶点，每个顶点的度不是5 5就是就是6 6。证明证明:G:G中至少有中至少有5 5个个6 6度顶点或至少有度顶点或至少有6 6个个5 5度顶点。度顶点。例例6 6 有有n n个药箱，若每两个药箱里有一种相同的药，个药箱，若每两个药箱里有一种相同的药，而每种药恰好放在两个药箱中，问药箱里共有多而每种药恰好放在两个药箱中，问药箱里共有多少种药？少种药？例例7 7 设设G G是有个是有个p p顶点，顶点，q q条边的无向图，各顶点的度条边的无向图，各顶点的度数均为数均为3 3。则。则 (1)(1)若若q

5、=3p-6,q=3p-6,证明证明:G:G在同构意义下唯一，并求在同构意义下唯一，并求p,qp,q。 (2)(2)若若p=6p=6，证明，证明:G:G在同构的意义下不唯一。在同构的意义下不唯一。例例8 8 已知已知p p阶阶( (简单简单) )无向图中有无向图中有q q条边，各顶点的度数条边，各顶点的度数 均为均为3 3，又，又2p=q+32p=q+3，试画出满足条件的所有不同，试画出满足条件的所有不同 构的构的G G。例例9 9 9 9个学生，每个学生向其他学生中的个学生，每个学生向其他学生中的3 3个学生各送个学生各送一张贺年卡。确定能否使每个学生收到的卡均来自一张贺年卡。确定能否使每个学

6、生收到的卡均来自其送过卡的相同人？为什么？其送过卡的相同人？为什么？解解: :否，不存在否，不存在9 9（奇数）个顶点的（奇数）个顶点的3 3正则图。正则图。习题课习题课 2 2例例1010 若若G G是一个恰有两个奇度顶点是一个恰有两个奇度顶点u u和和v v的无向图，则的无向图，则 （1 1）顶点）顶点u u与与v v连通；（连通；（2 2）G G连通连通G+uvG+uv连通。连通。例例1 1 设设G G为为p p阶简单无向图，阶简单无向图，p p2 2且且p p为奇数，为奇数，G G和和G G的的补图补图G GC C 中度数为奇数的顶点的个数是否一定相等？中度数为奇数的顶点的个数是否一定

7、相等？试证明你的结论。试证明你的结论。例例2 2 设设V=vV=v1 1,v,v2 2, ,v,vp p ，计算以，计算以V V为顶点集的无向图为顶点集的无向图的个数是多少？的个数是多少？(K(KP P有多少个生成子图有多少个生成子图) )例例3 3 设设V=vV=v1 1,v,v2 2, ,v,vp p,qp(p-1)/2,qp(p-1)/2，计算以，计算以V V为顶为顶点集具有点集具有q q条边的无向图的个数是多少？条边的无向图的个数是多少？例例4 4 设设G G是（是（p,qp,q）图，）图，rqrq，则具有，则具有r r条边的条边的G G的生成的生成子图有多少？子图有多少？答案：答案：

8、 2 2p(p-1)/2 p(p-1)/2 ，C Cq qp(p-1)/2p(p-1)/2 ，C Cr rq q。例例5 5 证明：若无向图证明：若无向图G G是不连通的，则是不连通的，则G G的补图的补图G GC C是连是连通的。（逆命题不成立）通的。（逆命题不成立）例例6 6 将无向完全图将无向完全图K K6 6的边随意地涂上红色或绿色的边随意地涂上红色或绿色, ,证明证明: :无论何种涂法无论何种涂法, ,总有红色的总有红色的K K3 3或绿色或绿色K K3 3。例例7 7 给无向完全图给无向完全图Kp(p7)Kp(p7)的各边随意地涂上红色或的各边随意地涂上红色或绿色，若已知从某点绿色

9、，若已知从某点v v0 0引出的引出的p-1p-1条边中至少有条边中至少有6 6条边条边涂红色，则涂红色，则KpKp存在红色的存在红色的K K4 4或绿色的或绿色的K K3 3。例例8 8 有有1717位学者，每位学者，每2 2位讨论位讨论3 3篇论文中的一篇且仅一篇论文中的一篇且仅一篇，证明：至少有篇，证明：至少有3 3位学者，他们相互讨论的是同一篇位学者，他们相互讨论的是同一篇论文。论文。习题习题3 3例例1 1 设设p p，q q为正整数，则为正整数，则（1 1）p p为何值时，无向完全图为何值时，无向完全图KpKp是欧拉图？是欧拉图？p p为何值为何值时时KpKp为半欧拉图？为半欧拉图

10、？（2 2）p,qp,q为何值时为何值时Kp,qKp,q为欧拉图？为欧拉图？ （3 3）p,qp,q为何值时为何值时Kp,qKp,q为哈密顿图？为哈密顿图？（4 4）p p为何值时，轮图为何值时，轮图WpWp为欧拉图？为欧拉图？例例2 2 判断如图所示的图是否为哈密顿图，若是写出哈判断如图所示的图是否为哈密顿图，若是写出哈密顿圈，否则证明其不是哈密顿图。密顿圈，否则证明其不是哈密顿图。abcdefgjhiabcdefghij 例例3 3 给出一个给出一个1010个顶点的非哈密顿图的例子，使得每个顶点的非哈密顿图的例子，使得每一对不邻接的顶点一对不邻接的顶点u u和和v v，均有，均有degu+

11、degv9degu+degv9。例例4 4 证明：完全图证明：完全图K K9 9中至少存在彼此无公共边的两条中至少存在彼此无公共边的两条哈密顿回路和一条哈密顿路？哈密顿回路和一条哈密顿路？例例5 5 试求试求KpKp中不同的哈密顿圈的个数。中不同的哈密顿圈的个数。例例6 6(1) (1) 证明具有奇数顶点的偶图不是哈密顿图；用证明具有奇数顶点的偶图不是哈密顿图；用此结论证明如图所示的图不是哈密顿图。此结论证明如图所示的图不是哈密顿图。 (2) (2) 完全偶图完全偶图K Km,nm,n为哈密顿图的充要条件是什么为哈密顿图的充要条件是什么？例例7 7 菱形菱形1212面体的表面上有无哈密顿回路？

12、面体的表面上有无哈密顿回路？例例8 8设设G=(V,E)G=(V,E)是连通图且顶点数为是连通图且顶点数为p,p,最小度数为最小度数为，若若p2p2, ,则则G G中有一长至少为中有一长至少为2 2的路。的路。例例9 9 证明：彼德森图不是哈密顿图。证明：彼德森图不是哈密顿图。例例1010 某工厂生产由某工厂生产由6 6种不同颜色的纱织成的双色布。种不同颜色的纱织成的双色布。双色布中，每一种颜色至少和其他双色布中，每一种颜色至少和其他3 3种颜色搭配。证种颜色搭配。证明明: :可以挑出可以挑出3 3种不同的双色布种不同的双色布, ,它们含有所有它们含有所有6 6种颜色。种颜色。与例与例8 8等

13、价的例题：等价的例题：例例1111 今要将今要将6 6个人分成个人分成3 3组（每组组（每组2 2个人）去完成个人）去完成3 3项项任务，已知每个人至少与其余任务，已知每个人至少与其余5 5个人中的个人中的3 3个人能相互个人能相互合作，问：合作，问： (1)(1)能否使得每组能否使得每组2 2个人都能相互合作？个人都能相互合作？ (2)(2)你能给出集中方案？（两种）你能给出集中方案？（两种）例例1212 设设G=(V,E)G=(V,E)是是p(p3)p(p3)个顶点的简单无向图个顶点的简单无向图, ,设设G G中中最长路最长路L L的长度为的长度为l(l2)l(l2)，起点与终点分别为，起

14、点与终点分别为u,vu,v，而且而且degu+degvpdegu+degvp。证明：。证明：G G中必有与中必有与L L不完全相同但不完全相同但长度也为长度也为L L的路。的路。例例1313 某公司来了某公司来了9 9名新雇员，工作时间不能互相交谈。名新雇员，工作时间不能互相交谈。为了尽快互相了解，他们决定利用每天吃午饭时间相为了尽快互相了解，他们决定利用每天吃午饭时间相互交谈。于是，每天在吃午饭时他们围在一张圆桌旁互交谈。于是，每天在吃午饭时他们围在一张圆桌旁坐下，他们是这样安排的，每一次每人的左、右邻均坐下，他们是这样安排的，每一次每人的左、右邻均与以前的人不同。问这样的安排法能坚持多久？

15、与以前的人不同。问这样的安排法能坚持多久？例例1414 已知已知a,b,c,d,e,f,g7a,b,c,d,e,f,g7个人中，个人中，a a会讲英语；会讲英语；b b会会讲英语和汉语；讲英语和汉语；c c会讲英语、意大利语和俄语；会讲英语、意大利语和俄语；d d会讲会讲汉语和日语；汉语和日语；e e会讲意大利语和德语；会讲意大利语和德语；f f会讲俄语、日会讲俄语、日语和法语；语和法语；g g会讲德语和法语。能否将他们的座位安会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？排在圆桌旁，使得每个人都能与他身边的人交谈？例例15 15 设设G G为为p p个顶点的简

16、单无向图。个顶点的简单无向图。 (1) (1) 若若G G的边数的边数q= (p-1)q= (p-1)(p-2)/2+2(p-2)/2+2，证明，证明G G为为哈密顿图。哈密顿图。 (2) (2) 若若G G的边数的边数q= (p-1)q= (p-1)(p-2)/2+1(p-2)/2+1，则，则G G是否是否一定为哈密顿图？一定为哈密顿图？例例16 16 如图所示的图如图所示的图G G是哈密顿图。试证明：若图中是哈密顿图。试证明：若图中的哈密顿回路中含边的哈密顿回路中含边e e1 1，则它一定同时也含，则它一定同时也含e e2 2。例例17 17 已知已知9 9个人个人v v1 1,v,v2

17、2, ,v,v9 9，其中，其中v v1 1和两个人握过手，和两个人握过手，v v2 2,v,v3 3,v,v4 4,v,v5 5各和各和3 3个人握过手，个人握过手，v v6 6和和4 4个人握过手，个人握过手，v v7 7,v,v8 8各和各和5 5个人握过手，个人握过手，v v9 9和和6 6个人握过手。证明个人握过手。证明: :这这9 9个人中一定可以找出个人中一定可以找出3 3个人互相握过手。个人互相握过手。例例1818某次会议有某次会议有2020人参加，其中每个人都至少有人参加，其中每个人都至少有1010个朋友，这个朋友，这2020人围一圆桌入席，要想使与每个人相人围一圆桌入席，要

18、想使与每个人相邻的两位都是朋友是否可能？根据什么？邻的两位都是朋友是否可能？根据什么？例例1919 设设G G是一个有是一个有p(p3)p(p3)个顶点的连通图。个顶点的连通图。u u和和v v是是G G的两个不邻接的顶点的两个不邻接的顶点, ,并且并且degu+degvpdegu+degvp 。证明：。证明：G G是哈密顿图是哈密顿图G+uvG+uv是是哈密顿图。哈密顿图。第六章第六章 树和割集树和割集( (习题课习题课1)1)例例1 1 若无向图若无向图G G中有个中有个p p顶点，顶点，p-1p-1条边，则条边，则G G为树。这为树。这个命题正确吗？为什么？个命题正确吗？为什么？例例2

19、2画出具有画出具有4 4、5 5、6 6、7 7个顶点的所有非同构的无向树。个顶点的所有非同构的无向树。例例3 3 设无向图设无向图G G是由是由K(K2)K(K2)棵树构成的森林，至少在棵树构成的森林，至少在G G中添加多少条边才能使中添加多少条边才能使G G成为一棵树？成为一棵树？例例4 4 设设T T是一棵树，是一棵树，T T有有3 3个度为个度为3 3顶点，顶点，1 1个个2 2度顶点，度顶点，其余均是其余均是1 1度顶点。则度顶点。则(1)(1)求求T T有几个有几个1 1度顶点？度顶点？(2)(2)画出满足上述要求的不同构的两棵树。画出满足上述要求的不同构的两棵树。例例5 5 设树

20、设树T T中有中有2n2n个度为个度为1 1的顶点，有的顶点，有3n3n个度为个度为2 2的顶点，的顶点，有有n n个度为个度为3 3的顶点，则这棵树的顶点，则这棵树T T有多少个顶点和多少条有多少个顶点和多少条边？边？例例6 6设设T T是一棵树且是一棵树且(T)(T)k k ，证明，证明:T:T中至少有中至少有k k个度个度为为1 1的顶点。的顶点。例例7 7证明证明: :恰有两个顶点度数为恰有两个顶点度数为1 1的树必为一条通路。的树必为一条通路。 例例8 8(1)(1)一棵无向树有一棵无向树有nini个度数为个度数为i i的顶点的顶点,i=1,2,i=1,2,k,k。n2,n3,n2,

21、n3,.nk.nk均为已知数，问均为已知数，问n1n1应为多少？应为多少？(2)(2)在在(1)(1)中，若中，若nr(3nr(3r rk)k)未知，未知，nj(jnj(jr)r)均为已知均为已知数，问数，问nrnr应为多少？应为多少？例例9 9 设无向图设无向图G G中有中有p p个顶点，个顶点，q-1q-1条边，则条边，则G G为连通图为连通图当且仅当当且仅当G G中无回路。中无回路。 例例1010设设G G是一个是一个(p,q)(p,q)图图, ,证明证明: :若若q qp,p,则则G G中必有圈。中必有圈。例例1111设设d1,d2,d1,d2,dp,dp是是p p个正整数个正整数,p

22、,p2, ,且且 。证明证明: :存在一棵顶点度数为存在一棵顶点度数为d1,d2,d1,d2,dp,dp的树。的树。例例1212证明证明: :任一非平凡树最长路的两个端点都是树叶。任一非平凡树最长路的两个端点都是树叶。122piidp例例1 1 设图设图G G中有中有9 9个顶点，每个顶点的度不是个顶点，每个顶点的度不是5 5就是就是6 6。证明证明:G:G中至少有中至少有5 5个个6 6度顶点或至少有度顶点或至少有6 6个个5 5度顶点。度顶点。例例2 2 设设G G是有个是有个p p顶点，顶点，q q条边的无向图，各顶点的度条边的无向图，各顶点的度数均为数均为3 3。则。则 (1)(1)若

23、若q=3p-6,q=3p-6,证明证明:G:G在同构意义下唯一，并求在同构意义下唯一，并求p,qp,q。 (2)(2)若若p=6p=6，证明，证明:G:G在同构的意义下不唯一。在同构的意义下不唯一。例例3 3 已知已知p p阶阶( (简单简单) )无向图中有无向图中有q q条边，各顶点的度数条边，各顶点的度数 均为均为3 3，又，又2p=q+32p=q+3，试画出满足条件的所有不同，试画出满足条件的所有不同 构的构的G G。习题课习题课例例设设G G是连通图，满足下面条件之一的边应具有什是连通图，满足下面条件之一的边应具有什么性质么性质 ？（1 1）在）在G G的任何生成树中；的任何生成树中；

24、（2 2）不在）不在G G的任何生成树中。的任何生成树中。例例2 2 非平凡无向连通图非平凡无向连通图G G是树当且仅当是树当且仅当G G的的每条边都的的每条边都是桥。是桥。例例3 3 设设T T是一棵树，是一棵树，p2p2 ，则，则（1 1）p p个顶点的树至多有多少个割点；个顶点的树至多有多少个割点；（2 2）p p个顶点的树有多少个桥？个顶点的树有多少个桥？例例4 4 证明或否定断言：连通图证明或否定断言：连通图G G的任意边是的任意边是G G的某一棵的某一棵生成树的弦。生成树的弦。例例5 5 设设T T是连通图是连通图G G中的一棵生成树，证明：中的一棵生成树，证明：T T的补中的补中

25、不含中任何割集。不含中任何割集。TT的补就是的补就是T T的弦的弦 TGT第七章习题课第七章习题课定理定理1 1 设设G=(V1V2G=(V1V2，E)E)是一个偶图，是一个偶图，|V1|V2|V1|V2|。G G中存在从中存在从V1V1到到V2V2的完全匹配的完全匹配是是V1V1中任意中任意k k个顶点个顶点(k=1,2,(k=1,2, |V1|), |V1|)至少与至少与V2V2中的中的k k个顶点相连接。个顶点相连接。例例现有现有4 4名教师：张、王、李、赵，要求他们去教名教师：张、王、李、赵，要求他们去教4 4门课程：数学、物理、电工和计算机科学。已知张门课程：数学、物理、电工和计算机

26、科学。已知张能教数学和计算机科学；王能教物理和电工；李能能教数学和计算机科学；王能教物理和电工；李能教数学、物理和电工；赵只能教电工。如何安排才教数学、物理和电工；赵只能教电工。如何安排才能使能使4 4位教师都能教课，并且每门课都有人教？共有位教师都能教课，并且每门课都有人教？共有几种方案？几种方案？用用相异性条件相异性条件判断一个偶图判断一个偶图是否存在完全匹配是否存在完全匹配常常很不方便，下面的充分条件比较便于实际应用。常常很不方便，下面的充分条件比较便于实际应用。定理定理2 2 设设G=(V1V2G=(V1V2，E)E)是一个偶图，是一个偶图，|V1|V2|V1|V2|。G G中存在从中

27、存在从V1V1到到V2V2的完全匹配的的完全匹配的充分条件充分条件是存在正整数是存在正整数t t，使得，使得V1V1中每个顶点的度大于等于中每个顶点的度大于等于t t，V2V2中每个顶点中每个顶点的度小于等于的度小于等于t t。该条件称为该条件称为t t条件。条件。例例某年级共开设某年级共开设7 7门课程，由门课程，由7 7位教师承担。已知每位教师承担。已知每位教师都能担任其中的位教师都能担任其中的3 3门课程。他们将自己能担任门课程。他们将自己能担任的课程报到教务处后，教务处人员发现每门课都恰好的课程报到教务处后，教务处人员发现每门课都恰好有有3 3位教师能担任。问教务处人员能否安排这位教师

28、能担任。问教务处人员能否安排这7 7位教师位教师每人担任每人担任1 1门课，并且每门课都有人承担。门课，并且每门课都有人承担。定理定理3 3 从从t t条件可以推出相异性条件。条件可以推出相异性条件。注意：注意：定理定理3 3中反过来不能推出中反过来不能推出t t条件。条件。推论推论1 1 任何任何r-r-正则偶图正则偶图G G(V1V2,E)(V1V2,E)必有一个完美必有一个完美匹配，其中匹配，其中r1r1。第七章平面图和图的着色第七章平面图和图的着色习题课习题课1.1.设设G G是有是有k k个分支、个分支、f f个面的个面的(p,q)(p,q)平面图，则平面图，则p-q+f=k+1p-

29、q+f=k+1。2.2.证明：下列证明：下列4 4个图均是可平面图。个图均是可平面图。3 3如图所示的图如图所示的图G G是否为平面图？是否为极大平面图？是否为平面图？是否为极大平面图？为什么？为什么？4.4.证明：极大平面图证明：极大平面图G G一定是连通图。一定是连通图。5. 5. 设设G G是有是有p(p3)p(p3)个顶点的简单平面连通图，且个顶点的简单平面连通图，且G G的的每个面均是由每个面均是由3 3条边围成，证明：条边围成，证明：G G是极大平面图。是极大平面图。（若（若G G是极大平面图，则是极大平面图，则G G的每个面都是三角形）的每个面都是三角形）6. 6. 由由6 6个

30、顶点，个顶点，1212条边构成的平面连通图条边构成的平面连通图G G中，每个中，每个面由几条边围成？为什么？面由几条边围成？为什么？7 7证明：若每个顶点的度数大于等于证明：若每个顶点的度数大于等于3 3时，则不存在时，则不存在有有7 7条边的平面连通图。条边的平面连通图。( (等价命题：证明：不存在等价命题：证明：不存在7 7条棱的凸多面体条棱的凸多面体) )8. 8. 设设G G是顶点是顶点p11p11的平面图，证明：的平面图，证明：G G的补图的补图G Gc c是非平是非平面图。面图。( (设设G G是顶点是顶点p11p11的图，证明：的图，证明：G G与与G G的补图的补图G Gc c

31、至少有一个是非平至少有一个是非平面图。面图。) )9.9.设设G G是平面连通图，顶点为是平面连通图，顶点为p p面数面数f f，证明，证明: :(1)(1)若若p3p3，则，则f2p-4f2p-4。(2)(2)若若(G)=4,(G)=4,则则G G中至少有中至少有6 6个顶点的度数个顶点的度数55。1010设设G G是边数是边数q30q30的平面图的平面图, ,证明证明:G:G中存在顶点中存在顶点v v， 使得使得degvdegv4 4。习题课习题课 2 21. 1. 说明图中所示图说明图中所示图(1)(2)(1)(2)是否是非平面图？是否是非平面图？2 2证明证明: :彼得森图不是平面图。

32、彼得森图不是平面图。 (1) (1) 收缩法；收缩法；(2) (2) 欧拉公式法；欧拉公式法；(3)(3)收缩到收缩到K K3,33,3。3.3.设设G G是无向图是无向图,p8,p8,则则G G与与G Gc c中至少有一个是平面图。中至少有一个是平面图。4.4.设平面图设平面图G G的顶点数的顶点数p=7,p=7,边数边数q=15q=15，证明，证明G G是连通的。是连通的。习习 题题 课课 3 31 1判断下面命题是否正确，并说明理由。判断下面命题是否正确，并说明理由。 任意平面图任意平面图G G的对偶图的对偶图G G* *的对偶图的对偶图G G* * *与与G G同构。同构。2. 2.

33、设设G G* *是平面图是平面图G G的对偶图，证明：的对偶图，证明：p p* *=f=f，q q* *=q=q， f f* *=p-k+1=p-k+1。其中。其中k(k1)k(k1)为为G G的连通分支数。的连通分支数。3. 3. 证明：若证明：若G G是自对偶的平面图，则是自对偶的平面图，则q=2p-2q=2p-2。其中。其中p p和和q q是是G G的边与顶点数。的边与顶点数。4 4把平面分成把平面分成p p个区域，每两个区域都相邻，问个区域，每两个区域都相邻，问p p最最大为多少？大为多少？5.5.证明：不存在具有证明：不存在具有5 5个面，每两个面都共享一条公个面，每两个面都共享一条

34、公共边的平面图共边的平面图G G。习题课习题课 4 41 1求下列各类图顶点的色数。求下列各类图顶点的色数。 (1)p (1)p阶零图阶零图Np;(2)Np;(2)完全图完全图Kp;(3)pKp;(3)p阶轮图阶轮图Wp(Wp(轮图至少轮图至少有有4 4个顶点个顶点);(4);(4)彼德森图彼德森图( (如图如图1 1所示所示);(5);(5)如图如图2 2所示。所示。2.2.若图若图G G的色数（或顶点色数）的色数（或顶点色数）K(G)=kK(G)=k，则，则G G中至少有中至少有k(k-1)/2k(k-1)/2条边。条边。3.3.设设G G是一个没有三角形的平面图，则是一个没有三角形的平面

35、图，则（1 1）证明：）证明：G G中存在一个顶点中存在一个顶点v v，使得，使得degv3degv3；（2 2）证明：）证明：G G是是4-4-可着色的。可着色的。4.5 4.5 四色问题四色问题 在图论中，也许是全部数学中，最著名、最难的问题是四在图论中，也许是全部数学中，最著名、最难的问题是四色猜想。色猜想。 这个猜想说，这个猜想说，在一个平面或球面上的任何地图能够只用四在一个平面或球面上的任何地图能够只用四种颜色来着色，使没有两个相邻的国家有相同的颜色。种颜色来着色，使没有两个相邻的国家有相同的颜色。 在这里，每个国家必须是一个单连通区域构成，两个国家在这里，每个国家必须是一个单连通区

36、域构成，两个国家相邻是指它们有一段公共边界线，不能只有一个公共点。相邻是指它们有一段公共边界线，不能只有一个公共点。 18521852年，弗朗西斯年，弗朗西斯. .古特利（嘉思瑞）（古特利（嘉思瑞）（GuthrieGuthrie）兄弟在）兄弟在通信中提出了四色问题，小古特利求教与他的老师通信中提出了四色问题，小古特利求教与他的老师德摩根德摩根（De De morganmorgan），德摩根与他的朋友在通信中讨论过这个问题，但他），德摩根与他的朋友在通信中讨论过这个问题，但他们都无法给予解决。们都无法给予解决。 18781878年凯莱（年凯莱（CayleyCayley）在伦敦数学大会上宣布了这个

37、问题，）在伦敦数学大会上宣布了这个问题，引起了数学界的广泛注意。引起了数学界的广泛注意。 18791879年肯普（年肯普（KempeKempe）、）、18801880年年TaitTait发表论文，声称证明发表论文，声称证明了四色问题。了四色问题。 18901890年，希伍德（年，希伍德（HeawoodHeawood）指出了肯普（）指出了肯普（KempeKempe）证）证明明中的一处错误，但却利用肯普（中的一处错误，但却利用肯普（KempeKempe）的方法）的方法证明了五色证明了五色定理成立。定理成立。 肯普（肯普（KempeKempe）的这个错误使得他的论证是不完全的。）的这个错误使得他的论

38、证是不完全的。不过，不过，应当指出的是应当指出的是: :肯普（肯普（KempeKempe）推理路线是）推理路线是19761976年美国年美国的阿普尔的阿普尔(K.Appel)(K.Appel)、黑肯、黑肯(W.Haken)(W.Haken)和考齐和考齐(J.Koch)(J.Koch)等等3 3人人所给出的成功证明的基础。所给出的成功证明的基础。 18911891年，彼德森（年，彼德森（PetersenPetersen）指出了）指出了TaitTait证明中所存在证明中所存在的错误，但的错误，但TaitTait的方法也有其合理部分。的方法也有其合理部分。 经过了一百年之后，这个貌似简单的经过了一百

39、年之后，这个貌似简单的四色猜想四色猜想才被美国才被美国的阿普尔的阿普尔(K.Appel)(K.Appel)、黑肯、黑肯(W.Haken)(W.Haken)和考齐和考齐(J.Koch)(J.Koch)等等3 3人人在在19761976年借助于计算机用了年借助于计算机用了12001200多个小时，多个小时，100100亿个逻辑判亿个逻辑判断才证明了四色定理。从而断才证明了四色定理。从而四色猜想成了四色定理。四色猜想成了四色定理。这个证这个证明引起了广泛的争论，主要是因为计算机在这里起到的重要明引起了广泛的争论，主要是因为计算机在这里起到的重要作用。作用。然而然而,四色定理的数学方法的证明还是一个没

40、有解决的问题。四色定理的数学方法的证明还是一个没有解决的问题。1.怎样证明程序的正确性？怎样证明程序的正确性？ 计算机证明不能显示，因此证明的正确性不能被接受。计算机证明不能显示，因此证明的正确性不能被接受。 2.在计算机程序里有没有导致不正确的结果的错误；在计算机程序里有没有导致不正确的结果的错误； 假如他们的证明依赖于或许不可靠的计算机输出，那么假如他们的证明依赖于或许不可靠的计算机输出，那么它是不是真正的证明。它是不是真正的证明。3. 100亿个逻辑判断就一定能把所有的可能都包括进去吗？亿个逻辑判断就一定能把所有的可能都包括进去吗？ 第十章第十章 习题课习题课例例1 1有向图仅有一个顶点

41、入度为有向图仅有一个顶点入度为0 0，其余顶点的入度均，其余顶点的入度均为为1 1，则一定是有向树吗？，则一定是有向树吗？例例2设设T=(V,A)T=(V,A)是一个有根树是一个有根树, ,其每个顶点的出度不是其每个顶点的出度不是0 0就是就是2 2。若。若T T有有n0n0个叶子，试求个叶子，试求T T的弧的条数。的弧的条数。例例3 3 设有根树有设有根树有1717条弧条弧,12,12片叶子片叶子,4,4个个4 4度顶点度顶点,1,1个个3 3度顶点度顶点, ,则则（1 1）求）求T T的树根的度数；的树根的度数；（2 2）画出满足此要求的有根树。）画出满足此要求的有根树。例例4 4 设设T

42、=(V,A)T=(V,A)是一个正则二元树是一个正则二元树, ,若若T T有有n0n0个叶子，个叶子，试求的弧的条数。试求的弧的条数。例例5 5 设设T T是有是有n0n0个叶子的正则二元树，个叶子的正则二元树，n2n2个出度为个出度为2 2的的顶点，证明：顶点，证明：n0=n2+1n0=n2+1。例例6 6 设设T T是有是有n0n0个叶子的个叶子的二元树二元树，出度为，出度为2 2的顶点为的顶点为n2n2，证明：证明：n0=n2+1n0=n2+1。例例7 7 有根树中最长有向路的两个端点都是树叶吗？有根树中最长有向路的两个端点都是树叶吗？为什么？为什么？例例8 8 设设T T是一个有是一个

43、有p p个顶点的正则二元树，求个顶点的正则二元树，求T T的叶子的叶子数，其中数，其中p p奇数。奇数。例例9 9(1)(1)证明证明: :正则正则( (满满) )二元树的叶子数比内点数大二元树的叶子数比内点数大1 1。 (2)(2)找出正则找出正则( (满满)m)m元树的叶子数的表达式，该表元树的叶子数的表达式，该表达式用树的内点数来表示。达式用树的内点数来表示。例例1010设设T T是一个正则是一个正则m m元树，它有元树，它有n0n0个叶子，则个叶子，则T T有多有多少条弧？少条弧？例例1111证明：任一棵正则证明：任一棵正则( (满满) )二元树必有奇数个顶点。二元树必有奇数个顶点。例例1212 设设T T为任一棵正则二元树，为任一棵正则二元树，q q为边数，为边数，n0n0为树叶为树叶数，证明：数，证明：q=2n0-2q=2n0-2。其中。其中n0n02 2。例例1313 设设T T为任一正则为任一正则m m元树，有元树，有n0n0个叶子，个叶子，n2n2个内点，个内点，则则(m-1)n2=n0-1(m-1)n2=n0-1。例例1414 每个比赛图必有一条有向哈密顿路（即有向生每个比赛图必有一条有向哈密顿路（即有向生成路）。成路）。 用数学归纳法证明每个比赛图中必有有向哈密顿路用数学归纳法证明每个比赛图中必有有向哈密顿路 精品课件精品课件！精品课件精品课件！