运筹学8图与网络分析课件.ppt

第八章 图与网络分析 主要内容： 8.1 图与网络的基本知识 8.1 图与网络基本知识 一、引言 1。产生 哥尼斯堡七桥难题 例8-1：哥尼斯堡七桥问题 哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？ 8.1 图与网络基本知识 数学家Euler在1736年解决： 8.1 图与网络基本知识 二、图与网络的基本概念 8.1 图与网络基本知识 8.1 图与网络基本知识 二、无向图的有关概念： 8.1 图与网络基本知识 二、无向图的有关概念： 8.1 图与网络基本知识 二、无向图的有关概念 8.1 图与网络基本知识 8.1 图与网络基本知识 例8-2：有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？ 8.1 图与网络基本知识 8.1 图与网络基本知识 树：一个无圈的无向连通图称为树。如果一个无圈的图中每一个分支都是树，则称图为森林。 8.1 图与网络基本知识 例8-4：一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。 8.1 图与网络基本知识 解：以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如C—E—A—F—D—B，就是一个符合要求的考试课程表。 8.1 图与网络基本知识 四、 树的概念 8.1 图与网络基本知识 四、 树的概念 求最小生成树的方法有破圈法和避圈法。 8.1 图与网络基本知识 五、欧拉回路与中国邮递员问题 8.1 图与网络基本知识 一笔划问题 8.1 图与网络基本知识 例8-3：哈密尔顿（Hamilton）回路是英国数学家哈密尔顿1857年提出。给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（并不要求经过每条边）。 8.1 图与网络基本知识 中国邮递员问题 8.1 图与网络基本知识 中国邮递员问题 奇偶点作业法：若图中无奇点，问题已解决； 8.1 图与网络基本知识 3）最优性判定：满足a)和b)两条。 8.2 最短路问题 三种算法求解三类最短路问题： （1）Dijkstra算法：求无负权网络最短路问题； 8.2 最短路问题 8.2 最短路问题 8.2 最短路问题 8.2 最短路问题 8.2 最短路问题 8.2 最短路问题 二、逐次逼近法 基本思想：令P1j表示从v1到vj的最短路长，P1i为v1到vi的最短路长，则必有下列方程： P1j=min(P1i+lij) 8.2 最短路问题 8.2 最短路问题 解：初始条件为： P11(1)=0， P12(1)=2， P13(1)=5， P14(1)=-3， P15(1)=P16(1)= P17(1)= P18(1)= ∞ 8.2 最短路问题 8.2 最短路问题 三、Floyd算法 8.2 最短路问题 三、Floyd算法 8.3 最大流问题 一、基本概念和基本定理 1。网络与流 定义： 对有向图G=(V，E)： vs –发点，vt – 收点，其余 -- 中间点 8.3 最大流问题 2。可行流与最大流 可行流满足： 8.3 最大流问题 3。增广链: 几个概念: 对可行流 8.3 最大流问题 增广链： 设f是一可行流，μ是从始点到终点的一条链，若μ满足下列条件，称其为一条增广链。 8.3 最大流问题 8.3 最大流问题 5。最大流-最小割定理 8.3 最大流问题 8.3 最大流问题 8.3 最大流问题 8.4 最小费用流问题 第一轮迭代： P11(2)=min{P11(1) +l11 ，P12(1) +l21 ， P13(1) +l31 ， P14(1) +l41 ， P15(1) +l51 ，P16(1) +l61 ，P17(1) +l71， P18(1) +l81 }=0 求解：见Excel表格求解。 P12(2)=min{P11(1) +l12 ，P12(1) +l22 ， P13(1) +l32 ， P14(1) +l42 ， P15(1) +l52 ，P16(1) +l62 ，P17(1) +l72， P18(1) +l82 }=2 依此类推。 10 10 10 15 M M 0 -1 M 3 M M M