[理学]上课图论-第一、二章.ppt

习题3 例1 设p，q为正整数，则 （1）p为何值时，无向完全图Kp是欧拉图？p为何值时Kp为半欧拉图？ （2）p,q为何值时Kp,q为欧拉图？ （3）p,q为何值时Kp,q为哈密顿图？ （4）p为何值时，轮图Wp为欧拉图？ (1.p≥3为奇数；p=2或(1);2.p,q≥2为偶数;3.p=q;4.不是） 例2 判断如图所示的图是否为哈密顿图，若是写出哈密顿圈，否则证明其不是哈密顿图。 例3 给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有degu+degv≥9。 例4 证明：完全图K9中至少存在彼此无公共边的两条哈密顿圈和一条哈密顿路？ 例5 试求Kp中不同的哈密顿圈的个数。 例6(1)证明具有奇数顶点的偶图不是哈密顿图；用此结论证明如图所示的图不是哈密顿图。 (2)完全偶图Km,n为哈密顿图的充要条件是什么？ 例7 证明：彼德森图不是哈密顿图。 例8 设G是一个有p(p≥3)个顶点的连通图。u和v是G的两个不邻接的顶点,并且degu+degv≥p 。证明： G是哈密顿图?G+uv是哈密顿图。 例9 已知a,b,c,d,e,f,g7个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？ 例10 某次会议有20人参加，其中每个人都至少有10个朋友，这20人围一圆桌入席，要想使与每个人相邻的两位都是朋友是否可能？根据什么？ 例11 设G为p个顶点的简单无向图。则 (1)若G的边数q=(p-1)·(p-2)/2+2，证明G为哈密顿图。 (2)若G的边数q=(p-1)·(p-2)/2+1，则G是否一定为哈密顿图？ 例12 图G是哈密顿图。试证明：若图中的哈密顿回路中含边e1，则它一定同时也含e2。 ⅰ 例13 已知9个人v1,v2,…,v9，其中v1和两个人握过手，v2,v3,v4,v5各和3个人握过手，v6和4个人握过手，v7,v8各和5个人握过手，v9和6个人握过手。证明:这9个人中一定可以找出3个人互相握过手。 例14 菱形12面体的表面上有无哈密顿回路？ 例15 设G=(V,E)是连通图且顶点数为p,最小度数为δ，若p2δ,则G中有一长至少为2δ的路。 例16 设G=(V,E)是p(p3)个顶点的简单无向图,设G中最长路L的长度为l(l≥2)，起点与终点分别为u,v，而且degu+degv≥p。证明：G中必有与L不完全相同但长度也为L的路。 第六章 树和割集 在图论中许多术语至今仍未统一。但是有一类图所用的术语却是相同的，这就是树。 1847年克希霍夫在研究电网络问题时提出了树、生成树的概念并发展了树的理论。 1857年凯莱(A·Cayley)在研究有机化学碳氢化合物的同分异构体时，也引用树，但他没有成功。 后来，把树作为一个纯数学的对象来研究是数学家约当(C·Jordan)。 1.树是一种非常简单的图，不仅对图论本身很重要的，而且树在不同的领域，特别是在计算机科学中具有更重要的应用。 2.本章研究树的数学性质、连通图的生成树及其应用。最后讨论割点、桥和割集等概念，并研究它们的性质。 第一节 树及其性质 1.1 树和森林 定义1连通且无圈的无向图称为无向树，简称树。 定义2没有圈的无向图称为无向森林，简称森林。 说明:(1) 森林是不连通的，但森林的每个支都是连通的，因此森林的每个支都是树。森林就是由若干棵树组成的图。 (2)仅有一个顶点的树称为平凡树。其他的树称为非平凡树。 (3)度为1的顶点称为树叶，度大于1的顶点称为(分)支点。 (4)注意，在图论中没有空图，因此也无空树。 1.2 树的特征性质(通过观察) 定理1设G=(V,E)是一个(p,q)图，则下列各命题等价： (1)G是树； (2)G的任两个不同顶点间有唯一的一条路联结； (3)G是连通的且p=q+1； (4)G中无圈且p=q+1； (5)G中无圈且G中任两个不邻接的顶点间加一条边，则得到有唯一圈的图； (6)G连通,并且若p≥3,则G不是Kp。又若G的任两个不邻接的顶点间加一条边,则得到恰有唯一圈的图。 推论1 任一非平凡树中至少有两个度为1的顶点。 证：设T为一棵非平凡的无向树，T中最长路L为: L:v1v2…vk，则端点v1与vk便是两个度为1的顶点。 假设v1不是度为1的顶点，则degv1≥2，于是v1除与v2邻接之外还应与另一顶点u邻接。 而若u在最长路L上，则会产生圈，与T是树矛盾。 而若u不在最长路L上，则会产生一条更长的路，这与L为最长路矛盾。故v1必为度为1的顶点。 同理，vk也是度为1的顶点。 推论2 任意非平凡树