图论讲稿演示

《图论讲稿演示》由会员分享，可在线阅读，更多相关《图论讲稿演示（104页珍藏版）》请在金锄头文库上搜索。

1、下回停1. 问题引入与分析2. 图论的基本概念3. 最短路问题及算法 图论模型4. 最小生成树及算法 5. 旅行售货员问题6. 模型建立与求解1. 问题引入与分析1) 98年全国大学生数学建模竞赛B题“最佳灾今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.情巡视路线”中的前两个问题是这样的：1）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线.2）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35

2、公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.公路边的数字为该路段的公里数.2) 问题分析：本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.将每个乡（镇）或村看作一个图的顶点，各乡 镇、村之间的公路看作此图对应顶点间的边，各条再回到点O，使得总权（路程或时间）最小.公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中 一类称之为旅行售货员问题，即在给定的加权网络 图中寻找从给定点O出发，行遍所有顶点至少一次如第一问是三个旅行售货员问题，第二问是四本题是旅行售货员问题的延伸多旅行售货员问题.

3、本题所求的分组巡视的最佳路线，也就是m条众所周知，旅行售货员问题属于NP完全问题，显然本问题更应属于NP完全问题. 有鉴于此，经过同一点并覆盖所有其他顶点又使边权之和达到 最小的闭链（闭迹）.个旅行售货员问题.即求解没有多项式时间算法.一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.2.图论的基本概念1) 图的概念2) 赋权图与子图3) 图的矩阵表示4) 图的顶点度5) 路和连通图论的发展什么是图?ABCD哥尼斯堡七桥示意图问题1(哥尼斯堡七桥问题):能否从任一陆地出发通过每座桥恰好一次而 回到出发点？ABDC七桥

4、问题模拟图欧拉指出：如果每块陆地所连接的桥都是偶数座，则 从任一陆地出发，必能通过每座桥恰好一次而 回到出发地.问题2(哈密顿环球旅行问题):十二面体的20个顶点代表世界上20个城市， 能否从某个城市出发在十二面体上依次经过每 个城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）问题3(四色问题):对任何一张地图进行着色，两个共同边界 的国家染不同的颜色，只需要四种颜色就够了.问题4(关键路径问题):一项工程任务,大到建造 一座大坝,一座体育中心,小至组装一台机床,一 架电视机, 都要包括许多工序.这些工序相互约 束,只有在某些工序完成之后, 一个工序才能开 始. 即它们之间存在完成的先后次

5、序关系,一般 认为这些关系是预知的, 而且也能够预计完成 每个工序所需要的时间. 这时工程领导人员迫切希望了解最少需要 多少时间才能够完成整个工程项目, 影响工程 进度的要害工序是哪几个？ 1) 图的概念定义 一个图G是指一个二元组(V(G),E(G)，其中: 其中元素称为图G的顶点.组成的集合，即称为边集,其中元素称为边.定义 图G的阶是指图的顶点数|V(G)|, 用来表示； 图的边的数目|E(G)|用 来表示. 也用来表示边是非空有限集，称为顶点集，1)2) E(G)是顶点集V(G)中的无序或有序的元素偶对表示图，简记 用定义 若一个图的顶点集和边集都是有限集，则称其为有限图. 只有一个顶

6、点的图称为平凡图，其他的所有图都称为非平凡图.定义若图G中的边均为有序偶对,称G为有向边 为无向边，称e连接 和 ，顶点 和 称图. 称边为有向边或弧,称是从 连接，称 为e的尾，称 为e的头. 若图G中的边均为无序偶对 ，称G为无向图.称为e的端点. 既有无向边又有有向边的图称为混合图.常用术语1) 边和它的两端点称为互相关联.2)与同一条边关联的两个端点称 为相邻的顶点，与同一个顶点 点关联的两条边称为相邻的边. 3) 端点重合为一点的边称为环，端点不相同的边称为连杆.4) 若一对顶点之间有两条以上的边联结，则这些边称为重边5) 既没有环也没有重边的图，称为简单图 常用术语 6) 任意两顶

7、点都相邻的简单图,称为完全图. 记为Kv. 7) 若 ， ，且X 中任意两顶点不，相邻，Y 中任意两顶点不相邻，则称为二部图或偶图；若X中每一顶点皆与Y 中一切顶点相邻,称为 完全二部图或完全偶图,记为 (m=|X|,n=|Y|)8) 图 叫做星.二部图2) 赋权图与子图 定义 若图 的每一条边e 都赋以 一个实数w(e)，称w(e)为边e的权，G 连同边上的权 称为赋权图.定义 设 和 是两个图.1) 若 ,称 是 的一个子图,记 2) 若 ， ，则称 是 的生成子图.3) 若 ，且 ，以 为顶点集，以两端点 均在 中的边的全体为边集的图 的子图，称 为 的由 导出的子图，记为 . 4) 若

8、 ，且 ，以 为边集，以 的端点集为顶点集的图 的子图，称为 的由 导出的边导出的子图，记为 . 3) 若 ，且 ，以 为顶点集，以两端点 均在 中的边的全体为边集的图 的子图，称 4) 若 ，且 ，以 为边集，以 的端点集为顶点集的图 的子图，称为 的由 导出的边导出的子图，记为 . 为 的由 导出的子图，记为 .3) 图的矩阵表示 邻接矩阵: 1) 对无向图 ，其邻接矩阵 ，其中： (以下均假设图为简单图).2) 对有向图 ,其邻接矩阵 ,其中： 其中：3) 对有向赋权图 , 其邻接矩阵 ,对于无向赋权图的邻接矩阵可类似定义. 关联矩阵 1) 对无向图 ，其关联矩阵 , 其中：2) 对有向

9、图 ，其关联矩阵 ,其中：4) 图的顶点度定义 1) 在无向图G中，与顶点v关联的边的数目(环 算两次),称为顶点v的度或次数，记为d(v)或 dG(v). 称度为奇数的顶点为奇点，度为偶数的顶点为偶点.2) 在有向图中，从顶点v引出的边的数目称为顶点v的出度，记为d+(v)，从顶点v引入的边的数目称为v的入度，记为d -(v). 称d(v)= d+(v)+d -(v)为顶点v的度或次数定理的个数为偶数推论 任何图中奇点5) 路和连通定义1) 无向图G的一条途径（或通道或链）是指 一个有限非空序列 ，它的项交替地为顶点和边，使得对 ， 的端点是 和 , 称W是从 到 的一条途径，或一条 途径.

10、 整 数k称为W的长. 顶点 和 分别称为的起点和终点 , 而 称为W的内部顶点.2) 若途径W的边互不相同但顶点可重复，则称W 为迹或简单链.3) 若途径W的顶点和边均互不相同，则称W为路 或路径. 一条起点为 ,终点为 的路称为 路 记为定义1) 途径 中由相继项构成子序列称为途径W的节.2) 起点与终点重合的途径称为闭途径.3) 起点与终点重合的的路称为圈(或回路)，长 为k的圈称为k阶圈，记为Ck.4) 若在图G中存在(u,v)路，则称顶点u和v在图G 中连通.5) 若在图G中顶点u和v是连通的，则顶点u和v之 之间的距离d(u,v)是指图G中最短(u,v)路的长；若没 没有路连接u和

11、v，则定义为无穷大.6) 图G中任意两点皆连通的图称为连通图 7) 对于有向图G，若 ，且 有类似地，可定义有向迹，有向路和有向圈.头 和尾 ，则称W为有向途径.例 在右图中：途径或链：迹或简单链：路或路径：圈或回路：转化：一人欲将一只狼,一头羊,一篮菜从河西 渡过河到河东.由于船小,一次只能带一物过河, 并且狼与羊,羊与菜不能独处.给出渡河方法.解：用四维0-1向量表示(人,狼,羊,菜)在 河西岸的状态(在河西岸则分量取1,否则取0), 共有24 =16 种状态.在河东岸的状态类似记作.由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不 允许的,从而对应状态(1,0,

12、0,1), (1,1,0,0), (1,0,0,0) 也是不允许的.以可允许的10个状态向量作为顶点,将可能 互相转移的状态用线段连接起来构成一个图.根据此图便可找到渡河方法.(1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0) (0,0,0,0) (0,0,0,1) (0,0,1,0) (0,1,0,0) (0,1,0,1)(0,1,0,1) (0,1,0,0) (0,0,1,0) (0,0,0,1) (0,0,0,0) (1,0,1,0) (1,0,1,1) (1,1,0,1) (1,1,1,0) (1,1,1,1) 河西=(人,狼,羊,菜)

13、河东=(人,狼,羊,菜)将10个顶点分别记为A1, A2, , A10 ,则渡河问 题化为在该图中求一条从A1到A10的路.从图中易得到两条路： A1 A6 A3 A7 A2 A8 A5 A10; A1 A6 A3 A9 A4 A8 A5 A10.3最短路问题及算法最短路问题是图论应用的基本问题，很多实际 问题，如线路的布设、运输安排、运输网络最小费用流等问题,都可通过建立最短路问题模型来求解.最短路的定义最短路问题的两种方法：Dijkstra和Floyd算法 .1) 求赋权图中从给定点到其余顶点的最短路 . 2) 求赋权图中任意两点间的最短路.2) 在赋权图G中，从顶点u到顶点v的具有最小权

14、定义 1) 若H是赋权图G的一个子图，则称H的各 边的权和 为H的权. 类似地，若称为路P的权若P(u,v)是赋权图G中从u到v的路,称的路P*(u,v)，称为u到v的最短路3) 把赋权图G中一条路的权称为它的长，把(u,v)路的最小权称为u和v之间的距离，并记作 d(u,v). 1) 赋权图中从给定点到其余顶点的最短路假设G为赋权有向图或无向图，G边上的权均非 负若 ，则规定 最短路是一条路，且最短路的任一节也是最短路求下面赋权图中顶点u0到其余顶点的最短路Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.1) 置 ，对 ， ， 且 .2) 对每个 ，用代替 ，计算 ，并把达到这个最小值的一个顶点记为 ，置3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2).Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.1) 置 ，对 ， ， 且 .2) 对每个 ，用代替 ，计算 ，并把达到这个最小值的一个顶点记为 ，置3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2).Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.1) 置 ，对 ， ， 且 .2) 对每个 ，用代替 ，计算 ，并把达到这个最小值的一个顶点记为 ，置3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2).Dijkst