图论实验精选课件.pptVIP

最短路问题 坚持 最短路径问题 例：求以下带权图从V0到V6最短路径。 权值表示两点之间的长度 坚持 起点多一条边出去 终点多一条边进入 其他点进入的边数等于出去的边数 坚持 （1）决策变量：Xij为弧（节点i到节点j）是否走，（1表示走， 0表示不走）。 （2）目标是通过网络的总长度最小，即从源点到 目标地的最短路 约束条件： 一个源（出发点）：净流量为1（表示开始）； 所有中间点：净流量为0（表示有走入必有走出）； 一个目的地（收点）：净流量为-1（表示结束） Xij非负 坚持 例1：从发电厂（记为节点1）向某城市（记为节点6）输送电，必须通过中转站（记为节点2，3，4，5）转送。图给出了两节点间的距离。电力公司希望选择合适的中转站，使从电厂到城市的传输路线最短。即从节点1到节点6的最短路径。这就是一个最短路问题。 坚持 用Excel求解最短路算法 净流量 = 流出该节点的流量 — 流入该节点的流量 中间节点的平衡值为0，起点为1，终点为-1。各个点的净流量等于平衡值 最短路平衡流 坚持 P(6)=8 P(5)=6 P(3)=3 P(1)=0 坚持 最大流问题 例：求以下带权有向图从V1到V4的最大流。 权值表示两点之间的流量限制 1 4 2 3 12 13 7 100 8 5 在一定条件下，使网络系统中从开始点到结束点之间的某种物资流的流量达到最大的问题。限制条件是每一条 边的最大通过能力（流量）。 坚持 除去源点和汇点的流量等于网络总流量之外，其他点所有流入的流量和流出的流量相等。 1 4 2 3 12 13 7 100 8 5 坚持 vs v2 v1 v3 vt 3 2 2 2 3 2 例2如下图所示，弧上数字表示该弧的容量，求该网络的最大流。 最大流量为从发点流出的量 坚持