十四次课图论课件

1、图论最早处理的问题是哥尼斯堡（konigsberg）城pregel河上的七桥问题。1736年，瑞士数学家 L.Eluer 在他发表的“哥尼斯堡七座桥”的著名文章中阐述了解决这个问题的观点，从而被誉为图论之父。 问题是这样的：在公元十八世纪的东普鲁士有个哥尼斯堡城（后属于苏联立陶宛苏维埃社会主义共和国，现名为加里宁格勒；现属于立陶宛共和国）。哥尼斯堡城位于pregel河畔，河中有两个岛，城市中的各个部分由七座桥相连。当时，城中的居民热衷于这样一个问题，从四块陆地的任一块出发，怎样才能做到经过每座桥一次且仅一次，然后回到出发点。问题看来并不复杂，但当地的居民和游人做了不少的尝试，却都没有取得成功。

2、8/9/20221Hongzhi Qiao, XiDian Univ.ABCD图 1图实际上是反映了客观事物之间的相互关系DCAB图 28/9/20222Hongzhi Qiao, XiDian Univ. 后来，在1736年，瑞士的数学家L.Euler解决了这个问题。他将四块陆地表示成四个结点，凡陆地间有桥相连的，便在两点间连一条线，这样图1就转化为图2了。此时，哥尼斯堡七桥问题归结为：在图2 所示的图中，从 A, B, C, D 任一点出发，通过每条边一次且仅一次而返回出发点的回路是否存在？ 欧拉断言这样的回路是不存在的。理由是：从图2中的任一点出发，为了要回到原来的出发点，要求与每个点相

3、关联的边数均为偶数。这样才能保证从一条边进入某点后，再从另一条边出去，从一个点的不同的两条边一进一出才能回到出发点，而图2中的A, B, C, D全是与奇数条边相连，由此可知所要求的回路是不可能存在的。 Leonhard Euler （1707-1783） 瑞士数学家8/9/20223Hongzhi Qiao, XiDian Univ.图/Graph： 可直观地表示离散对象之间的相互关系，研究它们的共性和特性，以便解决具体问题。第八章 - 图论 8/9/20224Hongzhi Qiao, XiDian Univ.8.1 图的概念/Introduction of Graph定义图 是一个非空有

4、限集，是上的一个二元关系，有序对（，）称为有向图/Directed Graph。 若将E中的有序对看成是无序的（即将e=(a,b)看成e=a,b），则称（，）为无向图/Undirected Graph。有向图和无向图统称为图/Graph ，记为G 。 G = （，）第八章 - 图论 8/9/20225Hongzhi Qiao, XiDian Univ.定义顶点： 中的元素称为顶点，用带标记的点表示，也称为结点/Vertices。定义边： 在有向图G中，若e=（，），e称为G的有向边/directed edge。用由到带箭头的线把和连起来； 在无向图G中，若e=（，），e称为G的无向边/undi

5、rected edge 。a、间用连线连结， 有向边和无向边统称为G的边/edge。第八章 - 图论 8/9/20226Hongzhi Qiao, XiDian Univ.8.2 图的术语/Graph Terminology定义相邻和关联： 在无向图G中，若e=（，） ，则称与b相邻/adjacent，或边e关联a、/incident或联结a、b/connect。a、b称为边e的端点或结束顶点/endpoint. 在有向图G中，若e=（，），即箭头由到，称相邻到，或a关联或联结b。a称为e的起点/initial vertex，b称为e的终点/terminal or end vertex。第八章

6、 - 图论 8/9/20227Hongzhi Qiao, XiDian Univ.定义自回路： 若（，），（，），称边（，）（，）是自回路/loop。定义孤立顶点： 若，不与其他顶点相邻，称为孤立顶点/isolated。第八章 - 图论 8/9/20228Hongzhi Qiao, XiDian Univ.定义顶点的次： 在无向图G中，与a相邻的顶点的数目称为a的次或度/degree。记为deg(a)或d(a)。 在有向图G中，以a为终点的边的条数称为a的入次或入度/in-degree。记为deg(a)或d (a)。以a为起点的边的条数称为a的出次或出度/out-degree。记为deg+(a

7、)或d +(a)。第八章 - 图论 8/9/20229Hongzhi Qiao, XiDian Univ.定理1 (Handshaking) 设无向图G=（V，E）有e条边，则G中所有顶点的次之和等于e的两倍。证明思路：利用数学归纳法。第八章 - 图论 8/9/202210Hongzhi Qiao, XiDian Univ.定理2 设有向图G=（V，E）有e条边，则G中所有顶点的入次之和等于所有顶点的出次之和，也等于e。证明思路：利用数学归纳法。第八章 - 图论 8/9/202211Hongzhi Qiao, XiDian Univ.有向图与无向图的对应： 无向图对应有向图：加上箭头。 有向图

8、对应无向图：去掉箭头。 称为underlying undirected graph第八章 - 图论 8/9/202212Hongzhi Qiao, XiDian Univ.定义子图： （，）是图，若（，）也是图且满足： (1)； (2)；则称为的子图/subgraph。注： 当时，称为的生成子图。 当时，或时称为的真子图。第八章 - 图论 8/9/202213Hongzhi Qiao, XiDian Univ.图 A图 B第八章 - 图论 8/9/202214Hongzhi Qiao, XiDian Univ.图 C图 D第八章 - 图论 8/9/202215Hongzhi Qiao, XiD

9、ian Univ.图是一个无向完全图图，均是的子图图的顶点是孤立顶点图的边，是孤立边图是图的子图（是完全图， 是的子图 )第八章 - 图论 8/9/202216Hongzhi Qiao, XiDian Univ. 例 G的真子图GG的生成子图GG8/9/202217Hongzhi Qiao, XiDian Univ.8.3图的表示与同构 Representing Graph and Graph Isomorphism图G表示的三种方法：（1）集合表示（2）邻接表（adjacency list）表示（3）矩阵（ matrix）表示 1、邻接矩阵（adjacency matrix）表示 2、关联矩

10、阵（incidence matrix）表示第八章 - 图论 8/9/202218Hongzhi Qiao, XiDian Univ.第八章 - 图论 8/9/202219Hongzhi Qiao, XiDian Univ. 上图中的四个图示，表面形状虽然不同，但这四个图示反映的结点的个数，边的条数，及结点与边之间的联系是相同的。若将(b)中的边v1, v3拉长，即可发现(b)与(a)是一个图。(c)只是将(a)中的结点换了个名字。而(d)也只是将(a)中的结点换了名字，且改变了边1, 3的位置。所以上图中的四个图示所反映的问题的实质是一样的。观察如下四个图示：v1v2v3v4v2v3v4v1u

11、1u4u3u21243(a)(b)(c)(d)8/9/202220Hongzhi Qiao, XiDian Univ.第八章 - 图论 8/9/202221Hongzhi Qiao, XiDian Univ.例：第八章 - 图论 8/9/202222Hongzhi Qiao, XiDian Univ.由上面的讨论不难看出，若两个图同构，它们必须满足:结点个数相等；边数相等；度数相同的结点个数相等。上面的三个条件只是两个图同构的必要条件，不是充分条件。上图中(a)，(b)两图示满足上述三个条件，但由于(a)中度数为3的结点v1与两个度数为1的结点v2， v3相邻，而在(b)中，度数为3的结点u1

12、只与一个度数为1的结点u2相邻，故(a)，(b) 不同构。v1v2v3u1u2(a)(b)8/9/202223Hongzhi Qiao, XiDian Univ. 从图中不容易直接得出。 可用邻接矩阵，通过某种算法确定两个图是否同构。上例的邻接矩阵：第八章 - 图论 8/9/202224Hongzhi Qiao, XiDian Univ.同构判定算法（用邻接矩阵）1、根据图确定其邻接矩阵（I)2、计算行次：矩阵每行的个数，（对应于出次） 和列次：（对应于入次）3、不考虑出现的次序不同，若行次与列次不同，则必不同构，否则继续 4、同时交换其一矩阵的行和行，列和列。 若此矩阵能变成与另一矩阵一样，

13、则同构。对所有顶点的排列都试过，仍不相同，则不同构。第八章 - 图论 8/9/202225Hongzhi Qiao, XiDian Univ.例： 把(II）的第行与第行交换，第列与第列交换，得:例：(1)的行次（，） 列次（，） (2)的行次（，） 列次（，）第八章 - 图论 8/9/202226Hongzhi Qiao, XiDian Univ.再把第行与第行交换，第列与第列交换，就得 : 第八章 - 图论 8/9/202227Hongzhi Qiao, XiDian Univ.7.4 连通性/Connectivity定义道路/path： 当中相邻边的序列（0，1），（1，2），（k-1，

14、k）称为一条道路（通路）。此道路的长度为。也可以以（0，1，k）表示道路，0为起点，k为终点。 当0=k时，该道路称为回路/circuit。第八章 - 图论 8/9/202228Hongzhi Qiao, XiDian Univ.定义简单道路/Simple Path： 一条道路中没有两条边是相同的，称此道路为简单道路。当其是回路时，称为简单回路/Simple Circuit。定义基本道路/Element Path： 一条道路中，除了起点和终点可以相同，没有其他相同顶点出现，称此道路为基本道路。当其是回路时，称为基本回路/Element Circuit。第八章 - 图论 8/9/202229Ho

15、ngzhi Qiao, XiDian Univ.（5，1 ，2 ，3，4）是简单道路，不是基本道路，因为（，）中，均出现了两次。但（c，d，b，c）是基本道路。第八章 - 图论 8/9/202230Hongzhi Qiao, XiDian Univ.定义连通性/connectivity： 设（，）， （0，1，k） 是G中的一条道路，则称0到k连通/connective或可达/。说明：对无向图而言，若0到k可达，则k到0也可达。对有向图而言则未必。第八章 - 图论 8/9/202231Hongzhi Qiao, XiDian Univ.定理1 任意一个连通无向图的任两个不同顶点都存在一条简单道

16、路。定义无向图的连通性： 若（，）中任两个不同顶点都连通，则称此无向图是连通的/connected。第八章 - 图论 8/9/202232Hongzhi Qiao, XiDian Univ.定义连通分图/connected components： 图可分为几个不相连通的子图，每一子图本身都是连通的。称这几个子图为的连通分图。定义无向图的连通性： 若（，）中任两个顶点都连通，则称此无向图是连通的/connected。第八章 - 图论 8/9/202233Hongzhi Qiao, XiDian Univ.定义有向图的连通性：(1)弱连通： 若（，）对应的无向图是连通图，则称为弱连通/weakly

17、 connected。(2）强连通： 若（，）中任两点间都有路，即对与，到可达，到可达，称为强连通/strongly connected。 第八章 - 图论 8/9/202234Hongzhi Qiao, XiDian Univ.第八章 - 图论 8/9/202235Hongzhi Qiao, XiDian Univ.第八章 - 图论 8/9/202236Hongzhi Qiao, XiDian Univ.例：用图描述一台自动售货机，只用分，分二种硬币，满分后压按钮，选择一块巧克力，钱多了不找还。第八章 - 图论 8/9/202237Hongzhi Qiao, XiDian Univ. 顶点：

18、 分边： ：投分 ：分 ：投分 ：分 ：压按扭动作 ：分 表示已投入钱的状态 表示一种动作自动售货机：有向加权图描绘得很清楚 （1）钱数不够，压按扭，不起作用 （2）钱数够了，压按扭，给过糖果回到分状态 （3）钱超过分，再加钱白加第八章 - 图论 8/9/202238Hongzhi Qiao, XiDian Univ.定义欧拉道路（回路）： （，），称包含中所有边的简单道路为欧拉道路/Euler Path/E道路。 包含中所有边的简单回路为欧拉回路/Euler Circuit/E回路。第八章 - 图论 8/9/202239Hongzhi Qiao, XiDian Univ.定理1（欧拉定理）：

19、 没有次为的孤立顶点的无向图存在欧拉道路的充要条件是： (1)图是连通的； (2)图中奇次顶点个数是个或2个。第八章 - 图论 8/9/202240Hongzhi Qiao, XiDian Univ.说明： 哥尼斯堡七桥问题，由于四个顶点都是奇次的，不可能有欧拉道路。应用与推广： （1） 一笔画问题； （2） 如果奇次顶点个数为2K个，此问题是K笔画问题。 第八章 - 图论 8/9/202241Hongzhi Qiao, XiDian Univ.例个顶点均为3次，至少要笔。定理2（有向图的欧拉定理）： 不含次为的孤立顶点的有向图具有欧拉道路的充要条件是：(1）弱连通；(2) 除了可能有个顶点，

20、一个入次比出次大，一个出次比入次大，其余顶点出次等于入次。第八章 - 图论 8/9/202242Hongzhi Qiao, XiDian Univ.中国邮递员问题 (欧拉道路的应用)(加权图)问题: 邮递员从邮局出发，走遍投递区域的所有街道，送完邮件后回到邮局，怎样使所走的路线全程最短. 若街道图（街道的交叉口为顶点）存在欧拉道路，显然此路是全程最短. 第八章 - 图论 8/9/202243Hongzhi Qiao, XiDian Univ.Hamilton(哈密顿)道路问题： 年发明的一种游戏。 在一个实心的正十二面体，20个顶点标上世界著名大城市的名字，要求游戏者从某一城市出发，遍历各城市

21、一次，最后回到原地。 这就是“绕行世界”问题。即找一条经过所有顶点（城市）的基本道路（回路）。第八章 - 图论 8/9/202244Hongzhi Qiao, XiDian Univ.定义哈密顿道路/回路： （，），G中经过中所有顶点的基本道路称为哈密顿道路/Hamilton Path，简称道路。 （，），G中经过中所有顶点的基本回路称为哈密顿回路/Hamilton Circuit，简称回路。第八章 - 图论 8/9/202245Hongzhi Qiao, XiDian Univ.图 每个顶点都是奇次的，不存在欧拉道路，但有道路。 图存在欧拉道路，不存在道路。第八章 - 图论 8/9/2022

22、46Hongzhi Qiao, XiDian Univ.定理3：设（，）是个顶点的简单图，如果任何一对顶点的次之和，则中一定有道路。注意: 此定理条件显然不是必要条件，如的边形，二个顶点次之和，而边形显然有道路。第八章 - 图论 8/9/202247Hongzhi Qiao, XiDian Univ.定理4： （，）是的简单图，若任何一对顶点的次之和，则必有哈密顿回路。定理5： 有向完全图一定存在道路。第八章 - 图论 8/9/202248Hongzhi Qiao, XiDian Univ. 要判别一个图不存在道路，回路，也不是很容易的，只能对无向图给出一些必要条件：（1）道路存在必要条件：

23、）连通 ）至多只能有二个顶点的次，其余顶点的次。bcda第八章 - 图论 8/9/202249Hongzhi Qiao, XiDian Univ.（2）回路存在必要条件： 对的任一非空真子集，的连通分图个数|。 第八章 - 图论 8/9/202250Hongzhi Qiao, XiDian Univ.解：取A1， A2 第八章 - 图论 8/9/202251Hongzhi Qiao, XiDian Univ.G存在3个分图 根据H道路存在的必要条件，可知：H道路不存在。第八章 - 图论 8/9/202252Hongzhi Qiao, XiDian Univ.8.6 最短道路问题 Shortes

24、t Path Problem加权图/Weighted graph G = （V，E，f ）, f:ER+ G满足简单连通无向第八章 - 图论 8/9/202253Hongzhi Qiao, XiDian Univ.应用问题：旅行商问题（TSP） Traveling Salesman Problem 问题：从某地出发，恰好一次经过个城市回到 原地，寻找最短的道路。实质：无向简单加权图，寻找最短回路的问题。说明： （1）不一定存在，若无向图是完全图则存在。 （2）图是连通的,两个城市间总有路,若以两城市间交通费用作为边的权,则是无向图的H回路问题.第八章 - 图论 8/9/202254Hongzhi Qiao, XiDian Univ.无向加权完全图的最近邻域算法/Approximation： 从任一顶点出发，记为1，找一个与1最近的顶点2，（1，2）为两个顶点的基本道路。 若找出有个顶点的基本道路