离散数学（第二版） 课件 邹丽娜 6 图论

离散数学第6章图论图的基本概念问题的提出:哥尼斯堡七桥问题ACBDl1l3l5l2l6l4l7哥尼斯堡桥问题之图示欧拉图问题的解决:欧拉图如果在每座桥上只通过一次（不走回头路）要走遍这七座桥，回到原来的出发点，是否可能？ABCDl5l2l1l3l4l7l6图的基本概念图：由图的顶点和边组成。

图的顶点：是平面上的点

图的边：是连结两个顶点之间的连线。一个图至少要有一个顶点，但一个图可以没有边。在一个图中，允许有多条边连接相同的两个顶点。ACBDl1l3l5l2l6l4l7图的基本概念

图的基本概念

例1:有四个城市：v1,v2,v3,v4，其中v1与v2间，v1与v4间,v2与v3间有直达长话线路相连，试将此事实用图的方法表示。解：可用图G=<V，E>表示图中的结点集为

V={v1,v2,v3,v4}

图中的边集为

E={(v1,v2),(v1,v4),(v2,v3)}v1v2v3v4(v1,v2)与(v2,v1)有相同的含义，即结点对(v1,v2)与次序无关

图的基本概念

例2:有四个程序：p1,p2,p3,p4，它们之间有一些调用关系：p1能调用p2；p2能调用p3；p2能调用p4；试将此事实用图的方法表示。解：可用图G=<V，E>表示图中的结点集为

V={p1,p2,p3,p4}

图中的边集为

E={(p1,p2),(p2,p3),(p2,p4)}(p1,p2)与(p2,p1)有不同的含义，即结点对(p1,p2)与次序有关p1p2p3p4

图的基本概念

图的分类:按边有无方向分类有向图：图中的所有边均为有向边无向图：图中的所有边均为无向边v1v3v2v'1v'2v'3有向图无向图点、边之间的关系邻接点：若存在边lk=(vi,vj)，称lk与结点vi及vj相关联，而vi与vj称为相邻接的。邻接边：若干条边关联于同一个结点，则这些边称为相邻环：一条边若与两个相同的结点相关联，则称为环。孤立点：不与任何结点相邻的结点称为孤立点。平行边：图中关联两个顶点的边多于1条。

图的基本概念

边lkvivjv1v2v4v3l1l2l3v1v3v4l1l3l4l2acbl图的基本概念简单图：不含平行边也不含环的无向图。多重图：含有平行边的无向图。完全图:一个(n,m)图G，如果其n个结点(n≥2)中的每一个均与其余n-1个结点邻接，则这样的图称为完全图。容易证明：n阶完全图有m=n(n-1)/2条边.【n阶完全图】含有个顶点的完全图称为阶完全图,记为Kn

图的基本概念

v1v3v2v4v1v5v4v2v3图的基本概念握手定理：图中结点的次数握手定理图G=<V,E>是一个(n,m)图，其中V={v1,v2,……,vn}，此时有分析：由定义知，结点v的度数等于以v为端点的边数，而1条边有2个端点(环的2个端点相同)，因此1条边贡献2度。证明：因为每条边都有两个端点(环的两个端点相同)，所以加上一条边就使得各结点的度数之和增加2，因此结论成立。例：在一次同学会上，想统计所有人握手次数之和，应该如何建立该问题的图论模型？练习是否存在无向图，其度数序列为：5，4，4，3，3，2，24，4，3，3，2，2所以度之和为偶数，即不能存在奇数个度为奇数的定点设无向图G有9条边，2个度为5的顶点，其余顶点度为2，则G的顶点总数为______。6图的矩阵表示例题6.51234561234561234512345例题6.5通路、回路与连通性问题的提出:右图是中国铁路交通图的一部分，如果一个旅客要从成都乘火车到北京，那么他一定会经过其它车站；而旅客不可能从成都乘火车到达台北。这就引出了图的通路与连通的概念。成都昆明重庆广州长沙武汉上海兰州西安沈阳北京天津郑州厦门高雄台北图的连通性图的连通性若通路中的边两两不同，则称该通路为简单通路。若通路经过的顶点各不相同，则称为初级通路若回路经过的边各不相同，则称为简单回路初级通路非初级的简单通路初级回路非初级的简单回路顶点之间的连通性定义:一个无向图G,如果它的任何两个结点均是可达的,则称图G为连通图;否则称为非连通图。v1v5v4v3v2v2v6v5v3v4v1v1v2v3v6v4v5连通图非连通图连通图计算两点间有多少条长为k的通路123123图中长为2的通路总数为：图中长为3的通路总数为：图中长为2的回路总数为：299213

v2到v3长为2的通路数为：v2到v3长为3的通路数为：315123123123123123123ABCbac求图中长度为2的通路总数求图中长度为2的回路总数求图中b、c之间长度为2的通路总数65020练习abcabcabcabc写出图的邻接矩阵，并计算图中长度为2的通路总数练习练习写出图的邻接矩阵，并计算图中长度为2的通路总数图的判定有向图出度:起点入度:终点【有向图的通路】

有向图的通路、回路、简单通路、简单回路、初级通路、初级回路、简单图等的定义都与无向图中的定义类似【有向图的顶点之间的连通性】弱连通的单向连通的不连通的弱连通的强连通的强连通：任何两结点间均是互相可达的；单向连通：任何两结点间至少有一向是可达的；弱连通：忽略边的方向后其无向图是连通的。连通性定义一个有向图，如果忽略其边的方向后得到的无向图是基图，基图是连通的则称此有向图为弱连通的，即连通；否则称为非连通图。【有向图的邻接矩阵】【计算有向图中两顶点间有多少条长为k的通路】

【判定有向图的两顶点间是否可达】

C*中没有0，所以在图6.19中任意两个顶点都相互可达所以是强连通图

v1v2v3v4

A=1100001010001020A2=1110100011003100A3=2110110011103310A4=3210111021104310v1到v2长为3的通路有条v1到v3长为3的通路有条v2到自身长为3的回路有条D中长为3的通路共有16条,其中回路4条11112341234v1v2v3v4A=1210001000010010A2=1231000100100001A3=1243001000010010A4=1264000100100001v1到v4长为3的通路有条,3v4到v1长为3的通路有条0v1到自身长为1,2,3,4的回路各有条1长为4的通路共有条，其中有条回路163长度小于等于4的回路共有条8该图是强连通图么？12341234练习欧拉图与哈密顿图——问题的引出哥尼斯堡七桥问题哥尼斯堡普莱格尔河【哥尼斯堡七桥问题】

历史上普鲁士有个哥尼斯堡镇，该镇被普雷格尔河支流分成四个部分。这四个部分包括河的两岸及河中心的两个小岛。在十八世纪人们用七座桥把这四个部分连接起来。每逢节假日，镇上的居民喜欢环城游玩，他们想弄明白是否有可能从镇里的某个位置出发不重复地经过所有桥并且返回出发地。哥尼斯堡七桥问题欧拉(Euler)将该问题抽象成点与线的连接图欧拉通路:经过图中所有顶点且每条边恰好经过一次的通路欧拉回路:经过图中所有顶点且每条边恰好经过一次的回路欧拉图:有欧拉回路的图顶点可以重复走边不可重复欧拉图欧拉图：图G的一个回路，若它通过G中的每条边一次，这样的回路称为欧拉回路。不是欧拉图欧拉图#PLAY不难看出：欧拉图是若干个边不重的圈之并。

下列哪个图具有欧拉通路？(a)(b)(c)(d)下列哪个图具有欧拉通路？ABCD提交单选题1分下面哪个图可以一笔画出来？ABCD提交多选题1分弹幕讨论为什么哥尼斯堡问题实现不了？欧拉图#欧拉通路：通过图G中的每条边一次的通路(非回路)。由定义可见图(a),(b),(d)有欧拉通路,(c)不是(a)(b)(c)(d)欧拉图欧拉通路欧拉回路欧拉图(1)yesyesyes(2)yesnono(3)nonono【欧拉图判定法则】图G包含欧拉通路当且仅当G连通且恰有两个奇数度顶点.且欧拉通路由其中的一个奇数度顶点出发，到另一个奇数度顶点结束即图G包含欧拉回路当且仅当G连通且每个顶点都是偶数度.判断下面的3个图中，是否是欧拉图？是否存在欧拉通路？v3v1v2v4(c)v3v1v2v4(a)v3v1v2v4(b)v3v1v2v4(f)v3v1v2v4(d)v3v1v2v4(e)练习不存在欧拉通路

不是欧拉图，但存在欧拉通路

欧拉图

欧拉图例1邮递员从邮局v1出发沿邮路投递信件，其邮路图如下图所示，试问是否存在一条投递路线使邮递员从邮局出发通过所有线路而不重复且最后回到邮局。v11v1v5v7v2v10v9v8v6v4v3v12解：此问题即为求证此图是否为欧拉图，由于图中每个结点均为偶数次，故由定理可知这样的一条投递路线是存在，实际上还可以将这条路线找出来。C:(v1,v5,v11,v7,v12,v8,v10,v6,v9,v11,v12,v10,v9,v5,v2,v6,v4,v8,v3,v7,v1)欧拉图的应用1---中国邮路问题

问题：一个邮递员从邮局出发，到所管辖的街道投递邮件，最后返回邮局，若必须走遍所辖各街道中每一条至少一次，则怎样选择投递路线使所走的路程最短？该问题求解思路包括三个方面：

1)G是欧拉图。

2)G具有欧拉通路（vi到vj）

3)若G中奇数度结点数多于2城市1城市2城市3vivj欧拉图例2洒水车从A点出发执行洒水任务，城市街道图形如图所示，试问是否存在一条洒水路线使洒水车从A点出发通过所有街道且不重复而最后回到车库B。解：此问题即为求证此图是否存在A到B的通路，由于图中每个结点除A、B为奇次数外均为偶数次，故由定理可知这样的一条洒水路线是存在，实际上还可以将这条路线找出来。P:(A,C,D,E,F,B,G,C,F,G,A,B)DECGFBA欧拉图的应用3----一笔画问题

具有欧拉回路和欧拉通路的图可以用一笔画出。欧拉图（回路）：从任意一点可以完成一笔画有欧拉通路的图：从奇数度顶点出发，到另一个奇数度顶点结束下面哪个图能用一笔画出来？

----含有欧拉通路、欧拉回路的图无欧拉通路欧拉图欧拉图有欧拉通路非欧拉图有欧拉通路非欧拉图无欧拉通路下面那些图是欧拉图？

----含有欧拉回路的图哥尼斯堡哈密顿图

(1)(2)问题的提出：是否能够在图1中找到一条回路，使它通过图中每个结点一次且仅一次，最后再回到出发地？即周游世界。问题的解决：哈密顿图哈密顿图定义

图G的一个回路，若它通过G中的每个结点一次，这样的回路称为哈密顿图回路。具有这种回路的图叫哈密顿图。通过中每个顶点一次且仅一次的通路称为哈密顿通路。通过中每个顶点一次且仅一次的回路称为哈密顿回路。哈密顿图:具有哈密顿回路的图.仅要求不重复的通过所有顶点，不要求边欧拉图要求不重复的通过所有边，顶点可重复汉密尔顿图美国图论数学家奥勒在1960年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密尔顿图。注意：上述是汉密顿图的充分条件，而不是必要条件。在六边形中，任两个不相邻的结点的度数之和都是4＜6，但六边形是哈密顿图。判断下面的3个图中，是