数学建模君友情提供财大培训课件图与网络.pptx

第五章图与网络模型;哥尼斯堡七桥问题

哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？;哥尼斯堡七桥问题;最后，数学家Euler（欧拉）在1736年巧妙地给出了这个问题的答案，并因此奠定了图论的基础，Euler把A、B、C、D四块陆地分别收缩成四个顶点，把桥表示成连接对应顶点之间的边，问题转化为从任意一点出发，能不能经过各边一次且仅一次，最后返回该点。这就是著名的Euler问题。;;图形必须是连通的。

2.每个点都与偶数条线相连;第1节基本概念;例2.在例1的人群中，把“相互认识”改为“认识”需要引入带箭头的连线，称为常记为;第2节最短路问题;例1.下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。;以上求从A到E的最短路径问题，可以转化为四个性质完全相

同，但规模较小的子问题，即分别从Di、Ci、Bi、A到E的最短路

径问题，分为四个阶段，并从后向前逆推，即运用逆序解法。

;第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点

和终点进行分析和讨论分别求C1，C2，C3到D1，D2的最短路

径问题：

表10-2

;第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分

析和讨论分别求B1,B2,B3,B4到C1,C2,C3的最短路径问题：

表10-3

;第一阶段：只有1个始点A，终点有B1,B2,B3,B4。对始点和终

点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：

表10-4

;以上计算过程及结果，可用图2表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。

;求最短路的狄克斯拉算法和福特算法：

1、狄克斯拉（Dijkstra）算法：适用于解决所有权数大于等于0的最短路问题，能求出起点v1到所有其它点vj的最短距离。

2、福特（Ford）算??：适用于有负权系数的最短路问题，能求出起点v1到所有其它点vj的最短距离。;Dijkstra算法（双标号法）;;例3电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）;解：这是一个求无向图的最短路的问题。可以把无向图的每一边（vi,vj）都用方向相反的两条弧（vi,vj）和（vj,vi）代替，就化为有向图，即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。

板书;树：无圈连通图。记为T＝T（V，E）.

给定一个无向图G=（V,E），保留G的所有点，而删除部分或保留部分G的边所获得的图称为G的生成子图；

若此生成子图T是一个树，则称T为生成树.;最小生成树：网络中边的权之和最小的生成树。

求最小生成树的破圈法

破圈法计算步骤：

①在网络图中寻找一个圈。若不存在圈，则已经得到最小生成树，或网络中不存在生成树；

②去掉该圈中权数最大的边；

反复重复①②两步，直到求出最小生成树。;1、破圈算法

①在图中寻找一个圈。若不存在圈，则已经得到生成树或该图不存在生成树；

②去掉该圈中一边；

反复重复①②两步，直到求出生成树。;例4、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,…,v7表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。;用破圈算法求前图中最小生成树的计算步骤：;练习：用破圈法求以下网络中的最小生成树。;第4节最大流问题;每一个节点流量平衡是指：;例6某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点