运筹学图与网络问题课件

第十一章图与网络模型

一、图与网络模型介绍二、最短路问题三、最小生成树问题四、最大流问题第十一章图与网络模型一、图与网络模型介绍一、图与网络模型介绍

1、引例一群人之间存在错综的关系：赵、钱、孙、李、周。赵与钱相互认识、与孙也相互认识；钱与孙相互认识、孙与李相互认识。他们与周都不认识。如何清晰的表示这些人之间的关系呢？当人数更多、人们间相互关系更复杂时，该怎样描述人们间的关系？一、图与网络模型介绍1、引例一群人之间存在错综的关系：赵、钱、孙、李、周。赵与钱相互认识、与孙也相互认识；钱与孙相互认识、孙与李相互认识。他们与周都不认识。赵钱孙李周一群人之间存在错综的关系：赵、钱、孙、李、周。赵与钱相互认识赵钱孙李周吴陈如果我们将上面的例子中人们之间的关系由“相互认识”改变成“认识”，如赵和周之间的关系是，周认识赵而赵不认识周，这时我们如何表达人们之间的这种关系呢？赵钱孙李周吴陈如果我们将上面的例子中人们之间的关系由“相互认用带箭头的线来表示人们之间的关系：赵孙周吴陈钱李用带箭头的线来表示人们之间的关系：赵孙周吴陈钱李一、图与网络模型介绍2、相关概念（1）点、边、弧（2）无向图、有向图（3）链、圈、连通图（4）路、回路（5）权、网络一、图与网络模型介绍2、相关概念点、边、弧点——用于表示各种事物，一般用V表示一个图中往往有多个点，一般用v1、v2、…表示。一个图中所有的n个点构成点集V={v1、v2、…、vn}边——用于描述事物间关系的线，一般用E表示。一个图中往往有多个边，一般用e1、e2、…表示。一个图中所有的n条边构成边集E={e1、e2、…、en}弧——带有箭头的线，一般用A表示。一个图中的n条弧，一般用a1、a2、…表示。一个图中所有的n条边构成边集A={a1、a2、…、an}点、边、弧点——用于表示各种事物，一般用V表示无向图、有向图无向图：由点和边构成的图，简称“图”，一般用G表示。G=（V，E），V是图G的点集，E是图G的边集。有向图：由点和弧构成的图，一般用D表示。D=（V，A），V是图D的点集，A是图D的弧集。无向图、有向图无向图：由点和边构成的图，简称“图”，一般用G链、圈、连通图链：对于无向图G来说，如果存在一个点、边交错序列（v1、e1、v2、e2、…、vn）,其中边ei的起点是vi，终点是vi+1，即ei=（vi，vi+1），则称这条点、边交错序列为联结v1，vn的链。圈：如果一条链（v1、e1、v2、e2、…、vn）中，v1=vn，则称之为圈连通图：对一个无向图G，若任何两个不同的点之间，至少存在一条链，则称G为连通图链、圈、连通图链：对于无向图G来说，如果存在一个点、边交错序路、回路路：在有向图D中，如果存在一个点、弧交错序列：（v1、a1、v2、a2、…、vn）,其中边ai的起点是vi，终点是vi+1，即ai=（vi，vi+1），则称这条点、弧交错序列为联结v1，vn的一条路。回路：如果路的第一个点和最后一个点相同，则称这条路为回路。路、回路路：在有向图D中，如果存在一个点、弧交错序列：（v权、网络权：当无向图G的每一条边（vi，vj），或有向图D的每一条弧（v’i，vj’）上都相应地有一个数来进一步说明点与点之间的关系，那么这样的数我们可以称之为权，记为wij。给无向图G或有向图D添加权的过程，通常称为赋权。网络：我们称赋了权的有向图D为网络。权、网络权：当无向图G的每一条边（vi，vj），或有向图D二、最短路问题最短路问题是对一个赋权的有向图D中的指定的两个点vs到vt找到一条从vs到vt的路，使得这条路上所有弧的权数的总和最小，这条路被称为从vs到vt的最短路，这条路上所有弧的权数的总和被称之为从vs到vt的距离。如下图，找出从v1到v4的最短路v1v2v3v442159v2二、最短路问题最短路问题是对一个赋权的有向图D中的指定的两个对下图，找出从vs到vt的最短路161617171822222323303031414159vsv1v2v3v4vt对下图，找出从vs到vt的最短路16161717182222例1求下图中v1到v6的最短路有向图D=（V，A），V={v1，v2，…，v6}A={(v1,v2)

，(v1,v4)，(v1,v3),(v2,v6),(v4,v2),(v4,v6),(v3,v5),(v3,v5),(v5,v4),(v5,v6)

}cij表示vi到vj的权v1v2v3v4v5v63252153571例1求下图中v1到v6的最短路有向图D=（V，A），v1例1求下图中v1到v6的最短路v1到vt的最短路步骤：1、给起点v1标号（0，s）2、确定已标号点集I，未标号点集J，找出弧集A={（vi,vj）|viI，vjJ}3、如果弧集A=空集，那么如果vt已标号，则结束，如果vt未标号则说明不存在从v1到vt的路。否则，如果弧集A≠空集，转44、对A中的弧，计算sij=li+cij,从中找出值最小的弧，给此弧标号为（sij，i）v1v2v3v4v5v63252153571双标号（sij，i）中sij表示由vi到vj的最短路长，i表示vi到vj的最短路上，此点前一个点的下角标。例1求下图中v1到v6的最短路v1到vt的最短路步骤：v例2电线公司准备在甲乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短。两地交通图如下：v1v2v3v4v5v61510326245176v7（甲）（乙）例2电线公司准备在甲乙两地沿路架设一条光缆线，问如何架设1、永久标号：v1（0，s）K=12、I={v1}，J={v2,v3,v4,v5,v6,v7}，A={(v1,v2)，(v1,v3)}3、A≠Ø4、s12=l1+c12=0+15=15s13=l1+c13=0+10=10Minsij=s13,永久标号：v3=（sij,i）=（10，1）v1v2v3v4v5v61510326245176v7（0，s）（10，1）1、永久标号：v1（0，s）v1v2v3v4v5v6151s12=l1+c12=0+15=15K=22、I={v1,v3}，J={v2,v4,v5,v6,v7}，A={(v1,v2)，(v3,v2)，(v3,v5)}3、A≠Ø4、s32=l3+c32=10+3=13s35=l3+c35=10+5=15Minsij=s32,永久标号：v2=（sij,i）=（13，3）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）s12=l1+c12=0+15=15v1v2v3v4v5v6s35=l3+c35=10+5=15K=32、I={v1,v2,v3}，J={v4,v5,v6,v7}，A={(v2,v7)，(v2,v4)，(v3,v5)}3、A≠Ø4、s27=l2+c27=13+17=30s24=l2+c24=13+6=19Minsij=s35,永久标号：v5=（sij,i）=（15，3）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）s35=l3+c35=10+5=15v1v2v3v4v5v6s27=l2+c27=13+17=30s24=l2+c24=13+6=19K=42、I={v1,v2,v3,v5}，J={v4,v6,v7}，A={(v2,v7)，(v2,v4)，(v5,v4),(v5,v6)}3、A≠Ø4、s54=l5+c54=15+4=19s56=l5+c56=15+2=17Minsij=s56,永久标号：v6=（sij,i）=（17，5）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）s27=l2+c27=13+17=30v1v2v3v4v5vs27=30s24=19s54=19K=52、I={v1,v2,v3,v5,v6}，J={v4,v7}，A={(v2,v7)，(v2,v4)，(v5,v4),(v6,v7)}3、A≠Ø4、s67=l6+c67=17+6=23Minsij=s24=s54,永久标号：v4=（sij,i）=（19，2）或（19，5）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2）/(19，5)s27=30s24=19s54=19v1vs27=30K=62、I={v1,v2,v3,v4,v5,v6}，J={v7}，A={(v2,v7)，(v4,v7)，(v6,v7)}3、A≠Ø4、s47=l4+c47=19+2=21s67=l6+c67=17+6=23Minsij=s47,永久标号：v7=（sij,i）=（21，4）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2）/(19，5)（21，4）s27=30v1v2v3v4v5v615103262V1到v7的最短路长为21，最短路径是v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2）/(19，5)（21，4）v7→v4→v2→v7→v4→v5→v3→v1v3→v1V1到v7的最短路长为21，最短路径是v1v2v3v4v5v三、最小生成树问题几个概念：树：无圈的连通图生成子图：给定一个无向图G=(V,E)，保留G中的所有点，删掉部分G的边，所得的新图G’就是G的生成子图。生成树：如果图G的生成子图是一个树，则称这个生成子图为生成树。最小生成树：在一个赋权的连通的无向图中，找出一个生成树，如果这个生成树的所有边的权数之和最小，那么这个树就叫做最小生成树。三、最小生成树问题几个概念：最小生成树求解方法一：破圈法算法步骤：1、在给定的赋权连通图上任找一圈2、在找到的圈中删掉一条权数最大的边3、如果余下的图不含圈，则它们构成最小生成树。最小生成树求解方法一：破圈法算法步骤：例4用破圈法求解下图的一个最小生成树v1v2v6v7v5v4v3103345341278例4用破圈法求解下图的一个最小生成树v1v2v6v7v5v例4用破圈法求解下图的一个最小生成树v1v2v6v7v5v4v3103345341278例4用破圈法求解下图的一个最小生成树v1v2v6v7v5v例4用破圈法求解下图的一个最小生成树v1v2v6v7v5v4v3103345341278最小生成树如图，总权数为19例4用破圈法求解下图的一个最小生成树v1v2v6v7v5v最小生成树求解方法一：避圈法算法步骤：1、另作一图G’，绘制原图G的所有顶点2、依次选取权数最小的边3、若在图G’中加入此边后不会产生圈，则在图G’中加入此边。否则在剩下的边中继续选取。最小生成树求解方法一：避圈法算法步骤：v1v2v6v7v5v4v3103345341278v1v2v6v7v5v4v3333127最小生成树如图，总权数为19v1v2v6v7v5v4v3103345341278v1v2四、最大流问题给了一个带发点和收点的网络，其每条弧的赋权表示容量。在不超过每条弧容量的前提下，求从发点到收点的最大流量。四、最大流问题给了一个带发点和收点的网络，其每条弧的赋权表示例6根据石油公司的管道网络，确定从v1到v7的最大流。v1v2v6v7v5v4v366321223254例6根据石油公司的管道网络，确定从v1到v7的最大流。vv1v2v6v7v5v4v3（0，6）（0，6）（0，3）（0，2）（0，1）（0，2）（0，2）（0，3）（0，2）（0，5）（0，4）v1v2v6v7v5v4v3（0，6）（0，6）（0，3）（v1v2v6v7v5v4v3（0，6）（0，6）（0，3）（0，2）（0，1）（0，2）（0，2）（0，3）（0，2）（0，5）（0，4）+2→

（2，4）（2，0）v1v2v6v7v5v4v3（0，6）（0，6）（0，3）（v1v2v6v7v5v4v3（0，6）（0，3）（0，1）（0，2）（0，2）（0，3）（0，2）（0，5）（0，4）+2→（2，0）（2，4）+3（3，3）（3，0）（3，2）v1v2v6v7v5v4v3（0，6）（0，3）（0，1）（v1v2v6v7v5v4v3（0，3）（0，1）（0，2）（0，2）（0，2）（0，4）+2→（2，0）（2，4）+3（3，3）（3，0）（3，2）+1（3，3）（1，0）（1，3）v1v2v6v7v5v4v3（0，3）（0，1）（0，2）（v1v2v6v7v5v4v3（0，3）（0，2）（0，2）（0，2）+2→（2，0）+3（3，3）（3，0）（3，2）+1（3，3）（1，0）（1，3）+2（5，1）（2，0）（2，0）（5，0）v1v2v6v7v5v4v3（0，3）（0，2）（0，2）（v1v2v6v7v5v4v3（0，3）（0，2）+2→（2，0）+3（3，0）+1（3，3）（1，0）（1，3）+2（5，1）（2，0）（2，0）（5，0）+2（5，1）（2，1）（2，0）（3，1）v1v2v6v7v5v4v3（0，3）（0，2）+2→（2v1v2v6v7v5v4v3+2→（2，0）+3（3，0）+1（1，0）+2（5，1）（2，0）（2，0）（5，0）+2（5，1）（2，1）（2，0）（3，1）v1v2v6v7v5v4v3+2→（2，0）+3（3，0）五、最小费用最大流问题最小费用最大流问题：给了一个带收发点的网络，对每一条弧（vi，vj），除了给出了容量cij外，还给出了这条弧的单位流量的费用bij，要求一个最大流F，并使得总费送费用最小。五、最小费用最大流问题最小费用最大流问题：给了一个带收发点的例7由于输油管道长短不一，所以例6中的每段管道除了有不同流量cij的限制外，还有不同的单位流量的费用bij，我们对每段管道（vi，vj）都用（cij，bij）。使用这个网络系统从v1向v7运送石油，怎样才能运送最多的石油，并使得总的运送费最小？v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）例7由于输油管道长短不一，所以例6中的每段管道除了有不同v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）（0，-6）（0，-3）（0，-4）（0，-5）（0，-2）（0，-3）（0，-8）（0，-4）（0，-3）（0，-7）（0，-4）v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）（0，-6）（0，-3）（0，-4）（0，-5）（0，-2）（0，-3）（0，-8）（0，-4）（0，-3）（0，-7）（0，-4）从发点到收点的增广路首选总的单位费用最小的路单位费用：101费用：1×10（5，3）（1，-3）（0，3）（1，-3）（3，4）（1，-4）v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（5，3）（3，2）（2，3）（0，3）（2，8）（3，4）（2，4）（0，-6）（1，-3）（0，-4）（0，-5）（0，-2）（1，-3）（0，-8）（0，-4）（0，-3）（0，-7）（1，-4）费用：1×101单位费用：11+2+2×11（3，3）（3，-3）（0，8）（2，-8）v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（3，3）（3，2）（2，3）（0，3）（0，8）（3，4）（2，4）（0，-6）（3，-3）（0，-4）（0，-5）（0，-2）（1，-3）（2，-8）（0，-4）（0，-3）（0，-7）（1，-4）1+2费用：1×10+2×11+2单位费用：12+2×12（1，3）（5，-3）（1，2）（2，-2）（0，3）（2，-3）（1，4）（3，-4）v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（1，3）（1，2）（0，3）（0，3）（0，8）（1，4）（2，4）（0，-6）（5，-3）（0，-4）（0，-5）（2，-2）（1，-3）（2，-8）（0，-4）（2，-3）（0，-7）（3，-4）1+2+2费用：1×10+2×11+2×12单位费用：16+1+1×16（0，3）（6，-3）（0，2）（2，-2）（1，4）（1，-4）（4，7）（1，-7）v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（v1v2v6v7v5v4v3（6，6）（3，4）（4，7）（2，5）（0，3）（0，2）（0，3）（0，3）（0，8）（1，4）（1，4）（0，-6）（6，-3）（0，-4）（0，-5）（3，-2）（1，-3）（2，-8）（1，-4）（2，-3）（1，-7）（3，-4）1+2+2+1费用：1×10+2×11+2×12+1×16单位费用：17+3+3×17（3，6）（3，-6）（0，4）（3，-4）（1，7）（4，-7）v1v2v6v7v5v4v3（6，6）（3，4）（4，7）（v1v2v6v7v5v4v3（3，6）（0，4）（1，7）（2，5）（0，3）（0，2）（0，3）（0，3）（0，8）（1，4）（1，4）（3，-6）（6，-3）（3，-4）（0，-5）（3，-2）（1，-3）（2，-8）（1，-4）（2，-3）（4，-7）（3，-4）1+2+2+1+3费用：1×10+2×11+2×12+1×16+3×17单位费用：22+1+1×22（2，6）（4，-6）（1，5）（1，-5）（0，4）（2，-4）（0，7）（5，-7）v1v2v6v7v5v4v3（3，6）（0，4）（1，7）（v1v2v6v7v5v4v3（0，4）（0，3）（0，2）（0，3）（0，3）（0，8）（1，4）（6，-3）（3，-4）（3，-2）（1，-3）（2，-8）（2，-3）（3，-4）10费用：1×10+2×11+2×12+1×16+3×17+1×22（2，6）（4，-6）（1，5）（1，-5）（0，4）（2，-4）（0，7）（5，-7）=145v1v2v6v7v5v4v3（0，4）（0，3）（0，2）（运筹学图与网络问题课件第十一章图与网络模型

一、图与网络模型介绍二、最短路问题三、最小生成树问题四、最大流问题第十一章图与网络模型一、图与网络模型介绍一、图与网络模型介绍

1、引例一群人之间存在错综的关系：赵、钱、孙、李、周。赵与钱相互认识、与孙也相互认识；钱与孙相互认识、孙与李相互认识。他们与周都不认识。如何清晰的表示这些人之间的关系呢？当人数更多、人们间相互关系更复杂时，该怎样描述人们间的关系？一、图与网络模型介绍1、引例一群人之间存在错综的关系：赵、钱、孙、李、周。赵与钱相互认识、与孙也相互认识；钱与孙相互认识、孙与李相互认识。他们与周都不认识。赵钱孙李周一群人之间存在错综的关系：赵、钱、孙、李、周。赵与钱相互认识赵钱孙李周吴陈如果我们将上面的例子中人们之间的关系由“相互认识”改变成“认识”，如赵和周之间的关系是，周认识赵而赵不认识周，这时我们如何表达人们之间的这种关系呢？赵钱孙李周吴陈如果我们将上面的例子中人们之间的关系由“相互认用带箭头的线来表示人们之间的关系：赵孙周吴陈钱李用带箭头的线来表示人们之间的关系：赵孙周吴陈钱李一、图与网络模型介绍2、相关概念（1）点、边、弧（2）无向图、有向图（3）链、圈、连通图（4）路、回路（5）权、网络一、图与网络模型介绍2、相关概念点、边、弧点——用于表示各种事物，一般用V表示一个图中往往有多个点，一般用v1、v2、…表示。一个图中所有的n个点构成点集V={v1、v2、…、vn}边——用于描述事物间关系的线，一般用E表示。一个图中往往有多个边，一般用e1、e2、…表示。一个图中所有的n条边构成边集E={e1、e2、…、en}弧——带有箭头的线，一般用A表示。一个图中的n条弧，一般用a1、a2、…表示。一个图中所有的n条边构成边集A={a1、a2、…、an}点、边、弧点——用于表示各种事物，一般用V表示无向图、有向图无向图：由点和边构成的图，简称“图”，一般用G表示。G=（V，E），V是图G的点集，E是图G的边集。有向图：由点和弧构成的图，一般用D表示。D=（V，A），V是图D的点集，A是图D的弧集。无向图、有向图无向图：由点和边构成的图，简称“图”，一般用G链、圈、连通图链：对于无向图G来说，如果存在一个点、边交错序列（v1、e1、v2、e2、…、vn）,其中边ei的起点是vi，终点是vi+1，即ei=（vi，vi+1），则称这条点、边交错序列为联结v1，vn的链。圈：如果一条链（v1、e1、v2、e2、…、vn）中，v1=vn，则称之为圈连通图：对一个无向图G，若任何两个不同的点之间，至少存在一条链，则称G为连通图链、圈、连通图链：对于无向图G来说，如果存在一个点、边交错序路、回路路：在有向图D中，如果存在一个点、弧交错序列：（v1、a1、v2、a2、…、vn）,其中边ai的起点是vi，终点是vi+1，即ai=（vi，vi+1），则称这条点、弧交错序列为联结v1，vn的一条路。回路：如果路的第一个点和最后一个点相同，则称这条路为回路。路、回路路：在有向图D中，如果存在一个点、弧交错序列：（v权、网络权：当无向图G的每一条边（vi，vj），或有向图D的每一条弧（v’i，vj’）上都相应地有一个数来进一步说明点与点之间的关系，那么这样的数我们可以称之为权，记为wij。给无向图G或有向图D添加权的过程，通常称为赋权。网络：我们称赋了权的有向图D为网络。权、网络权：当无向图G的每一条边（vi，vj），或有向图D二、最短路问题最短路问题是对一个赋权的有向图D中的指定的两个点vs到vt找到一条从vs到vt的路，使得这条路上所有弧的权数的总和最小，这条路被称为从vs到vt的最短路，这条路上所有弧的权数的总和被称之为从vs到vt的距离。如下图，找出从v1到v4的最短路v1v2v3v442159v2二、最短路问题最短路问题是对一个赋权的有向图D中的指定的两个对下图，找出从vs到vt的最短路161617171822222323303031414159vsv1v2v3v4vt对下图，找出从vs到vt的最短路16161717182222例1求下图中v1到v6的最短路有向图D=（V，A），V={v1，v2，…，v6}A={(v1,v2)

，(v1,v4)，(v1,v3),(v2,v6),(v4,v2),(v4,v6),(v3,v5),(v3,v5),(v5,v4),(v5,v6)

}cij表示vi到vj的权v1v2v3v4v5v63252153571例1求下图中v1到v6的最短路有向图D=（V，A），v1例1求下图中v1到v6的最短路v1到vt的最短路步骤：1、给起点v1标号（0，s）2、确定已标号点集I，未标号点集J，找出弧集A={（vi,vj）|viI，vjJ}3、如果弧集A=空集，那么如果vt已标号，则结束，如果vt未标号则说明不存在从v1到vt的路。否则，如果弧集A≠空集，转44、对A中的弧，计算sij=li+cij,从中找出值最小的弧，给此弧标号为（sij，i）v1v2v3v4v5v63252153571双标号（sij，i）中sij表示由vi到vj的最短路长，i表示vi到vj的最短路上，此点前一个点的下角标。例1求下图中v1到v6的最短路v1到vt的最短路步骤：v例2电线公司准备在甲乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短。两地交通图如下：v1v2v3v4v5v61510326245176v7（甲）（乙）例2电线公司准备在甲乙两地沿路架设一条光缆线，问如何架设1、永久标号：v1（0，s）K=12、I={v1}，J={v2,v3,v4,v5,v6,v7}，A={(v1,v2)，(v1,v3)}3、A≠Ø4、s12=l1+c12=0+15=15s13=l1+c13=0+10=10Minsij=s13,永久标号：v3=（sij,i）=（10，1）v1v2v3v4v5v61510326245176v7（0，s）（10，1）1、永久标号：v1（0，s）v1v2v3v4v5v6151s12=l1+c12=0+15=15K=22、I={v1,v3}，J={v2,v4,v5,v6,v7}，A={(v1,v2)，(v3,v2)，(v3,v5)}3、A≠Ø4、s32=l3+c32=10+3=13s35=l3+c35=10+5=15Minsij=s32,永久标号：v2=（sij,i）=（13，3）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）s12=l1+c12=0+15=15v1v2v3v4v5v6s35=l3+c35=10+5=15K=32、I={v1,v2,v3}，J={v4,v5,v6,v7}，A={(v2,v7)，(v2,v4)，(v3,v5)}3、A≠Ø4、s27=l2+c27=13+17=30s24=l2+c24=13+6=19Minsij=s35,永久标号：v5=（sij,i）=（15，3）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）s35=l3+c35=10+5=15v1v2v3v4v5v6s27=l2+c27=13+17=30s24=l2+c24=13+6=19K=42、I={v1,v2,v3,v5}，J={v4,v6,v7}，A={(v2,v7)，(v2,v4)，(v5,v4),(v5,v6)}3、A≠Ø4、s54=l5+c54=15+4=19s56=l5+c56=15+2=17Minsij=s56,永久标号：v6=（sij,i）=（17，5）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）s27=l2+c27=13+17=30v1v2v3v4v5vs27=30s24=19s54=19K=52、I={v1,v2,v3,v5,v6}，J={v4,v7}，A={(v2,v7)，(v2,v4)，(v5,v4),(v6,v7)}3、A≠Ø4、s67=l6+c67=17+6=23Minsij=s24=s54,永久标号：v4=（sij,i）=（19，2）或（19，5）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2）/(19，5)s27=30s24=19s54=19v1vs27=30K=62、I={v1,v2,v3,v4,v5,v6}，J={v7}，A={(v2,v7)，(v4,v7)，(v6,v7)}3、A≠Ø4、s47=l4+c47=19+2=21s67=l6+c67=17+6=23Minsij=s47,永久标号：v7=（sij,i）=（21，4）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2）/(19，5)（21，4）s27=30v1v2v3v4v5v615103262V1到v7的最短路长为21，最短路径是v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2）/(19，5)（21，4）v7→v4→v2→v7→v4→v5→v3→v1v3→v1V1到v7的最短路长为21，最短路径是v1v2v3v4v5v三、最小生成树问题几个概念：树：无圈的连通图生成子图：给定一个无向图G=(V,E)，保留G中的所有点，删掉部分G的边，所得的新图G’就是G的生成子图。生成树：如果图G的生成子图是一个树，则称这个生成子图为生成树。最小生成树：在一个赋权的连通的无向图中，找出一个生成树，如果这个生成树的所有边的权数之和最小，那么这个树就叫做最小生成树。三、最小生成树问题几个概念：最小生成树求解方法一：破圈法算法步骤：1、在给定的赋权连通图上任找一圈2、在找到的圈中删掉一条权数最大的边3、如果余下的图不含圈，则它们构成最小生成树。最小生成树求解方法一：破圈法算法步骤：例4用破圈法求解下图的一个最小生成树v1v2v6v7v5v4v3103345341278例4用破圈法求解下图的一个最小生成树v1v2v6v7v5v例4用破圈法求解下图的一个最小生成树v1v2v6v7v5v4v3103345341278例4用破圈法求解下图的一个最小生成树v1v2v6v7v5v例4用破圈法求解下图的一个最小生成树v1v2v6v7v5v4v3103345341278最小生成树如图，总权数为19例4用破圈法求解下图的一个最小生成树v1v2v6v7v5v最小生成树求解方法一：避圈法算法步骤：1、另作一图G’，绘制原图G的所有顶点2、依次选取权数最小的边3、若在图G’中加入此边后不会产生圈，则在图G’中加入此边。否则在剩下的边中继续选取。最小生成树求解方法一：避圈法算法步骤：v1v2v6v7v5v4v3103345341278v1v2v6v7v5v4v3333127最小生成树如图，总权数为19v1v2v6v7v5v4v3103345341278v1v2四、最大流问题给了一个带发点和收点的网络，其每条弧的赋权表示容量。在不超过每条弧容量的前提下，求从发点到收点的最大流量。四、最大流问题给了一个带发点和收点的网络，其每条弧的赋权表示例6根据石油公司的管道网络，确定从v1到v7的最大流。v1v2v6v7v5v4v366321223254例6根据石油公司的管道网络，确定从v1到v7的最大流。vv1v2v6v7v5v4v3（0，6）（0，6）（0，3）（0，2）（0，1）（0，2）（0，2）（0，3）（0，2）（0，5）（0，4）v1v2v6v7v5v4v3（0，6）（0，6）（0，3）（v1v2v6v7v5v4v3（0，6）（0，6）（0，3）（0，2）（0，1）（0，2）（0，2）（0，3）（0，2）（0，5）（0，4）+2→

（2，4）（2，0）v1v2v6v7v5v4v3（0，6）（0，6）（0，3）（v1v2v6v7v5v4v3（0，6）（0，3）（0，1）（0，2）（0，2）（0，3）（0，2）（0，5）（0，4）+2→（2，0）（2，4）+3（3，3）（3，0）（3，2）v1v2v6v7v5v4v3（0，6）（0，3）（0，1）（v1v2v6v7v5v4v3（0，3）（0，1）（0，2）（0，2）（0，2）（0，4）+2→（2，0）（2，4）+3（3，3）（3，0）（3，2）+1（3，3）（1，0）（1，3）v1v2v6v7v5v4v3（0，3）（0，1）（0，2）（v1v2v6v7v5v4v3（0，3）（0，2）（0，2）（0，2）+2→（2，0）+3（3，3）（3，0）（3，2）+1（3，3）（1，0）（1，3）+2（5，1）（2，0）（2，0）（5，0）v1v2v6v7v5v4v3（0，3）（0，2）（0，2）（v1v2v6v7v5v4v3（0，3）（0，2）+2→（2，0）+3（3，0）+1（3，3）（1，0）（1，3）+2（5，1）（2，0）（2，0）（5，0）+2（5，1）（2，1）（2，0）（3，1）v1v2v6v7v5v4v3（0，3）（0，2）+2→（2v1v2v6v7v5v4v3+2→（2，0）+3（3，0）+1（1，0）+2（5，1）（2，0）（2，0）（5，0）+2（5，1）（2，1）（2，0）（3，1）v1v2v6v7v5v4v3+2→（2，0）+3（3，0）五、最小费用最大流问题最小费用最大流问题：给了一个带收发点的网络，对每一条弧（vi，vj），除了给出了容量cij外，还给出了这条弧的单位流量的费用bij，要求一个最大流F，并使得总费送费用最小。五、最小费用最大流问题最小费用最大流问题：给了一个带收发点的例7由于输油管道长短不一，所以例6中的每段管道除了有不同流量cij的限制外，还有不同的单位流量的费用bij，我们对每段管道（vi，vj）都用（cij，bij）。使用这个网络系统从v1向v7运送石油，怎样才能运送最多的石油，并使得总的运送费最小？v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）例7由于输油管道长短不一，所以例6中的每段管道除了有不同v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）（0，-6）（0，-3）（0，-4）（0，-5）（0，-2）（0，-3）（0，-8）（0，-4）（0，-3）（0，-7）（0，-4）v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（