企业运筹学-图与网络理论讲义课件

运筹学第五章图与网络理论

交大管理学院杨民助运筹学第五章图与网络理论1图与网络理论图的概念网络概念网络最短树问题网络最短路问题网络最大流问题图与网络理论图的概念2图的概念什么是图图的概念

所谓图，就是顶点和边的集合，点的集合记为V，边的集合记为E，则图可以表示为：G＝（V，E），点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两个端点。在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。

图的概念什么是图图的概念3图的概念图的表示

e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念图的表示e1e2e3e44图的概念点与边

顶点数集合V中元素的个数，记作p(G)。

边数集合E中元素的个数，记作q(G)。若e=[u,v]∈E，则称u和v为e的端点，而称e为u和v的关联边，也称u，v与边e相关联。例如图5－1中的图G，p(G)=6，q(G)=9，v1，v2是e1和e2的端点，e1和e2都是v1和v2的关联边。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念点与边顶点数集合V中元素的个数，记作p(G5图的概念点边关系若点u和v与同一条边相关联，则u和v为相邻点；若两条边ei和ej有同一个端点，则称ei与ej为相邻边。例如在图5－1中v1和v2为相邻点，v1和v5不相邻；e1与e5为相邻边，e1和e7不相邻。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念点边关系若点u和v与同一条边相关联，则u和v为相6图的概念简单图若一条边的两个端点是同一个顶点，则称该边为环；又若两上端点之间有多于一条边，则称为多重边或平行边。例如图5－1的e8为环，e1，e2为两重边，e4，e5也是两重边。含有多重边的图称作多重图。无环也无多重边的图称作简单图。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念简单图若一条边的两个端点是同一个顶点，则称该边为7图的概念图的次次点v作为边的端点的次数，记作d(v)，如图5－1中，d(v1)=5,d(v4)=6等端点次为奇数的点称作奇点；次为偶数的点称作偶点。次为1的点称为悬挂点，与悬挂点连接的边称作悬挂边；次为0的点称为孤立点。图5－1中的点v5即为悬挂点，边e9即为悬挂边，而点v6则是弧立点。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念图的次次点v作为边的端点的次数，记作d(v)8图的概念定理1若图G中所有点都是孤立点，则称图G为空图。定理1所有顶点的次的和，等于所有边数的2倍。即e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念定理1若图G中所有点都是孤立点，则称图G为空图9图的概念定理2

定理2在任一图中，奇点的个数必为偶数。设V1和V2分别是图G中次数为奇数和偶数的顶点集合。由定理1有e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念定理2定理2在任一图中，奇点的个数必为偶数10图的概念链

由两两相邻的点及其相关联的边构成的点边序列称为链。v0称为链的起点，vn称为链的终点。若v0≠vn则称该链为开链，反之称为闭链或回路。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念链由两两相邻的点及其相关联的边构成的点边序列称11图的概念简单链

若链中所含的边均不相同，则称为简单链；若点均不相同，则称为初等链或通路。除起点和终点外点均不相同的闭链，称为初等回路或称为圈。例如图中e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9是一条链，且是开链，也是简单链，但不是初等链，因为v1出现两次。图的概念简单链若链中所含的边均不相同，则称为简单链；若12图的概念圈

若链中所含的边均不相同，则称为简单链；若点均不相同，则称为初等链或通路。除起点和终点外点均不相同的闭链，称为初等回路或称为圈。例如图中e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9是一个圈。图的概念圈若链中所含的边均不相同，则称为简单链；若点均13图的概念连通性

若一个图G的任意两点之间均至少有一条通路（初等链）连接起来，则称这个图G是一个连通图，否则称作不连通图。例如图中，v1和v6之间没有通路，因此它不是连通图，而如果去掉v6，则构成一个连通图。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念连通性若一个图G的任意两点之间均至少有一条通路14图的概念连通的意义

连通是一个很重要的概念，如果一个问题所对应的图是一个不连通图，则该问题一定可以分解成互不相关的子问题来加以研究，即可以把不连通图分解成连通的子图来研究。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念连通的意义连通是一个很重要的概念，如果一个问题15图的概念子图子图的定义设，G1=(V1,E1),

G2=(V2,E2)，如果V1V2，又E1E2，则称G1是G2的子图。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9e1e2e3e4e5v2v3v1必须指出，并不是从图G2中任选一些顶点和边在一起就组成G2的子图G1，而只有在G2中的一条边以及连接该边的两个端点均选入G1时，G1才是G2的子图。图的概念子图子图的定义设，G1=(V1,E1)16图的概念特殊子图当G1中不包含G2中所有的顶点和边，则称G1是G2的真子图。部分图若V1=V2，E1E2，则称G1为G2的一个部分图。若V1V2，E1={[u,v]|u∈V1,v∈V1}，则称G1是G2中由V1导出的导出子图。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9e1e2e3e4e5v2v3v1图的概念特殊子图当G1中不包含G2中所有的顶点和边，则17图的概念有向图在有些图中，边是没有方向的，即[u,v]=[v,u]，这种图称为无向图。而有些关系是不对称的，例如父子关系、上下级关系、加工工序的先后顺序等都具有单向性，用图来表示这些关系时，得到的边是具有方向的，用带箭头的线来表示，称为弧。从顶点u指向υ的弧a，记作＝a=(u,v),(u,v)≠(v,u)，其中u称为a的起点，v称为a的终点，这样的图称为有向图。仍以V表示点的集合，以A表示弧的集合，则有向图表示为D＝（V，A）图的概念有向图在有些图中，边是没有方向的，即[u,v]=18图的概念有向图例e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念有向图例e1e2e3e419图的概念有向图的链路有向图中，在不考虑边的方向时，也可以相同地定义链，若有向图D＝（V，A）中，P是一个从u到v的链，且对P中每一条弧而言，在序列中位于该弧前面的点恰好是其起点，而位于该弧后面的点恰好是其终点，这个链P就称为是D中从u到v的一条路。当路的起点与终点相同，即u=v时，称作一条回路。顶点全不相同的路称为初等路。除起点和终点外点均不相同的回路称为初等回路。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念有向图的链路有向图中，在不考虑边的方向时，也可20图的概念树一个没有圈的图称为一个无圈图或称为林。一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。定理以下关于树的六种不同描述是等价的：①无圈连通图。②无圈，q=p-1。③连通，q=p-1。④无圈，但若任意增加一条边，则可得到一个且仅一个圈。⑤连通，但若任意舍弃一条边，图便不连通。⑥每一对顶点之间有一条且仅有一条链。图的概念树一个没有圈的图称为一个无圈图或称为林。21图的概念部分树若T是图G＝（V，E）的部分图，且T是树，则称T为G的部分树。若T是图G的部分树，则从G中去掉T中所有的边，所得到的子图称为G中的T的余树，也称为G的一个余树。余数不一定是树！一个没有圈的图称为一个无圈图或称为林。一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。图的概念部分树若T是图G＝（V，E）的部分图，且T是树22网络概念图只能用来研究事物之间有没有某种关系，而不能研究这种关系的强弱程度。网络赋权的图权程度的度量，数量描述。

v1139538362v6

v5

v3

v4

v2网络概念图只能用来研究事物之间有没有某种关系，而不能研究这种23网络最短树问题最短树问题的一般提法是：选取网络中的部分图，使得网络连通，且使总权数最短。在实际应用中，经常碰到需要求一个赋权连通图的最短树的问题。例如，用节点表示城市，用边表示可以在两个城市之间架设光缆，边上的权表示光缆的长度，试求应如何架设光缆，才能使任意两城市之间均由光缆相通，且使光缆的总长度最短。求最短树的方法，依据的是树的特点，即无圈和连通，加上最短的要求，方法主要有两种：一种称为破圈法，一种称为生长法网络最短树问题最短树问题的一般提法是：选取网络中的部分图24树的概念回顾一个没有圈的图称为一个无圈图或称为林。一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。定理以下关于树的六种不同描述是等价的：①无圈连通图。②无圈，q=p-1。③连通，q=p-1。④无圈，但增加一条边，则可得到一个且仅有一个圈。⑤连通，但若舍弃一条边，图便不连通。⑥每一对顶点之间有一条且仅有一条链。树的概念回顾一个没有圈的图称为一个无圈图或称为林。25网络最短树破圈法原理方法原理如果网络图中无圈并且q=p-1，则已经是树；如果网络图中有圈，则截去该圈中权数最大的边；这样，并不影响网络图的连通性，且能使边数减少一个；经过一定次数的截边，网络图中将再也没有圈，成为无圈图；如果此时的网络满足q=p-1，则已经是树；由于每次截去的边在圈中具有最大的权数，因此获得的树也是最短的树。网络最短树破圈法原理26

v1139538362v6

v5

v3

v4

v2网络最短树破圈法方法步骤①在网络图中寻找一个圈，若已经无圈则转③。②在圈中选取权数最大的边，从网络图中截去该边，对新的网络，转①。③若q=p-1，则已找到最短树，否则网络图不连通，无最短树。方法示例：例5－4对图中的网络，用破圈法求最短树。

v1139538362v6v5v3v27网络最短树生长法原理

方法原理类似于自然界中植物生长的过程，结合就近生长和避免构成圈的要求，逐步生长直到所有的点都已经被包含。如果原网络不连通，则在生长过程中会出现某些点不能被生长，则结束。避圈的原理是已经被包含在生长过的树中的点不再被生长。由于在每次生长时都采用就近生长的方法，生成的树一定是最短树。网络最短树生长法原理28

v1139538362v6

v5

v3

v4

v2网络最短树生长法1方法步骤①从图上任选一点υi，令②从Sk中的各点到Sk中各点的边中选权数最小的边，设为[υi，υj]，则若这样的边不存在，则原图没有最短部分树。③令若S=V，则已找到最短树，否则②，v1139538362v6v5v3v29

v1139538362v6

v5

v3

v4

v2网络最短树生长法2方法示例取S={v1},则S到其余点的距离在距离矩阵中第一行v2v3v4v5v6S126∞∞∞V2389∞S2389∞v1139538362v6v5v3v30网络最短树生长法3方法示例v2v3v4v5v6S126∞∞∞V2389∞S2389∞V353∞S353∞V5∞1S451V63S53网络最短树生长法3方法示例v2v3v4v5v6S12631网络最短树生长法4v2v3v4v5v6S126∞∞∞V2389∞S2389∞V353∞S353∞V5∞1S451V63S53

v1139538362v6

v5

v3

v4

v2网络最短树生长法4v2v3v4v5v6S126∞∞∞V32网络最短路线问题最短路线问题的一般提法是：欲寻找网络中从起点υ1到终点υn的最短路线，即寻求连接这两点的边的总长度为最小的通路，最短路线中的网络大都是有向网络，也可以是无向网络。adbetcfs9757845646547图4-7网络最短路线问题最短路线问题的一般提法是：欲寻找网络中从33最短路问题的狄克斯拉算法把V分成两个集合令计算求若vk=vn则已经求得vn到v1的最短路线，否则继续计算使用条件lij≥0最短路问题的狄克斯拉算法把V分成两个集合令计算求若vk=v34算法解释若以p(vi)记v1到vi的最短距离，则根据动态规划原理应有第一步取P(v1)＝0，而T(vj)则是对P(vj)所取的初值；

v1139538362v6

v5

v3

v4

v2狄克斯拉算法1算法解释第一步取P(v1)＝0，而T(vj)则是对P(v35狄克斯拉算法2算法解释第二步利用P(vi)已知，据上式对T(vj)进行修正；

v1139538362v6

v5

v3

v4

v2狄克斯拉算法2算法解释第二步利用P(vi)已知，据上36狄克斯拉算法3算法解释第三步对T(vj)求

v1139538362v6

v5

v3

v4

v2狄克斯拉算法3算法解释第三步对T(vj)求v1137狄克斯拉算法4算法解释k=2,不是最优，继续

v1139538362v6

v5

v3

v4

v2狄克斯拉算法4算法解释k=2,不是最优，继续v1138狄克斯拉算法5算法解释在所有的T(vj)中确定最小的

v1139538362v6

v5

v3

v4

v2狄克斯拉算法5算法解释在所有的T(vj)中确定最小的39狄克斯拉算法6算法解释k=3,不是最优，继续

v1139538362v6

v5

v3

v4

v2狄克斯拉算法6算法解释k=3,不是最优，继续v1140狄克斯拉算法7算法解释k=5,不是最优，继续

v1139538362v6

v5

v3

v4

v2狄克斯拉算法7算法解释k=5,不是最优，继续v1141狄克斯拉算法8算法解释k=6=n,已经是最优。如果希望计算v1到v4的最短距离，继续

v1139538362v6

v5

v3

v4

v2狄克斯拉算法8算法解释k=6=n,已经是最优。如果希望计42狄克斯拉算法9表格实现vjv1v2v3v4v5v6初始值T(vj

)0∞∞∞∞∞

v1139538362v6

v5

v3

v4

v2第一次P()+lij0+20+60+∞0+∞0+∞T()26∞∞∞狄克斯拉算法9表格实现vjv1v2v3v4v5v6初始值T43狄克斯拉算法10表格实现vjv1v2v3v4v5v6初始值T(vj

)0∞∞∞∞∞第一次P()+lij0+20+60+∞0+∞0+∞T()26∞∞∞第二次P()+lij2+32+82+92+∞T()51011∞第三次P()+lij5+55+35+∞T()108∞第四次P()+lij8+∞8+1T()109狄克斯拉算法10表格实现vjv1v2v3v4v5v6初始值44福德算法1适用于有负权，但无负回路的有向或无向网络，其算法步骤如下：

令计算若对所有j则最优，否则把k的值加1，继续计算。若k=n-1，则说明存在负回路，最短路线不存在。福德算法1适用于有负权，但无负回路的有向或无向网络，其算法45福德算法2适用于有负权，但无负回路的有向或无向网络，算法中dj(k)为从υ1到υj的边数不超过k的路线中距离最短的。算法依据的思想是动态规划最优性原理，在此处形成递推公式。福德算法2适用于有负权，但无负回路的有向或无向网络，46福德算法3算法示例

v1139538362v6

v5

v3

v4

v2福德算法3算法示例v11395383647福德算法4

v1139538362v6

v5

v3

v4

v2026∞∞∞福德算法4v1139538362v6v48福德算法5

v1139538362v6

v5

v3

v4

v2026∞∞∞0福德算法5v1139538362v6v49福德算法6

v1139538362v6

v5

v3

v4

v2026∞∞∞02福德算法6v1139538362v6v50福德算法7

v1139538362v6

v5

v3

v4

v2026∞∞∞0225②福德算法7v1139538362v6v51福德算法8

v1139538362v6

v5

v3

v4

v2026∞∞∞0225②10②福德算法8v1139538362v6v52福德算法9

v1139538362v6

v5

v3

v4

v2026∞∞∞0225②10②9③福德算法9v1139538362v6v53福德算法10

v1139538362v6

v5

v3

v4

v2026∞∞∞0225②10②9③∞福德算法10v1139538362v654福德算法11

v1139538362v6

v5

v3

v4

v2026∞∞∞0225②10②9③∞025108③10⑤福德算法11v1139538362v655福德算法12

v1139538362v6

v5

v3

v4

v2026∞∞∞0225②10②9③∞025108③10⑤025108③9⑤福德算法12v1139538362v656福德算法13

v1139538362v6

v5

v3

v4

v2026∞∞∞0225②10②9③∞025108③10⑤025108③9⑤0251089福德算法13v1139538362v657最大流问题的概念所谓最大流问题就是在一定的条件下，要求流过网络的物流、能量流或信息流等流量为最大的问题，在最大流问题中一般有如下规定：①网络有一个起点υs和一个终点υt②网络是有向网络，即流有方向性。③在网络各条弧上都有一个权，表示允许流过的最大流量。若以bij表示由υi到υj的弧上允许流过的最大流量，以xij表示实际流过该弧的流量，则0≤xij≤bij④网络中，除起点υs和终点υt之外的任何顶点，流入量总和应该等于流出量的总和。

最大流问题的概念所谓最大流问题就是在一定的条件下，要求流过网58最大流问题的数学模型最大流问题的数学模型：

vs101165473915vt

v5

v3

v4

v2最大流问题的数学模型最大流vs10116547359最大流最小割集定理1网络中的最大流量fmax值大小是由网络中最狭窄处瓶颈的容量所决定的。

最大流－最小割集定理揭示了最小割集（网络中的瓶颈）容量与最大流量的关系，也提供了一个求最大流的方法。割集

网络割集容量最小割集所有割集中容量最小的一个割集。最大流最小割集定理1网络中的最大流量fmax值大小是由网络60最大流最小割集定理2网络中的最大流量fmax值大小是由网络中最狭窄处瓶颈的容量所决定的。

网络割集容量最小割集所有割集中容量最小的一个割集。最大流－最小割集定理流过网络的最大流量等于最小割集的容量。

最大流最小割集定理2网络中的最大流量fmax值大小是由网络61最大流最小割集定理3

vs

101165473915vt

v5

v3

v4

v2SS割集容量vsv2v3v4v5vt(vsv2)

(vsv3)24vsv2v3v4v5vt(vsv3)

(v2v4)(v2v5)20vsv3v2v4v5vt(vsv2)

(v3v2)(v3v4)

(v3v5)29………..…最大流最小割集定理3vs1011654762福德－富克逊方法原理算法的原理首先，依据最大流问题的要求，为网络分配一个可行流。所谓可行流，是指所有弧上流量满足容量限制，所有中间点满足平衡条件的流；若这一可行流的流量就是最大流量，则问题已经解决；若不是最大流量，则增加流量获得流量更大的可行流。福德－富克逊方法原理算法的原理63福德－富克逊方法流图

求一个初始可行流

是判断初始可行流是否最优结束

不是

求使目标得到改善的可行流福德－富克逊方法流图

64福德－富克逊方法图示算法原理图示初始流初始流福德－富克逊方法图示65福德－富克逊方法讨论若弧(vi,vj)上的流量满足xij=bij，则称该弧为饱和弧，否则称为非饱和弧。若弧(vi,vj)上的流量xij=0。则称该弧为零流弧，否则称为非零流弧。一条从υs到υt的初等链是由υs开始的点、边序列，其中没有相同的点，也不考虑弧的方向。把这条链中的υs到υt方向相同的弧称为正向弧。把这条链中的υs到υt方向相反的弧称为逆向弧。在上述的可行流中，从υs到υt的某个初等链满足：①其上的正向弧均为非饱和弧。②其上的逆向弧均为非零流弧。则称该链为一条流量增广链。福德－富克逊方法讨论若弧(vi,vj)上的流量满足66福德－富克逊方法讨论流量增广链:从υs到υt的某个初等链满足①其上的正向弧均为非饱和弧。②其上的逆向弧均为非零流弧。结论：若在可行流中，存在从υs到υt的增广链，则该可行流不是最大流，其流量可以增加；否则若不存在从υs到υt的增广链，则该可行流是最大流。

福德－富克逊方法讨论流量增广链:从υs到υt的某个初等67增广链的性质流量增广链:从υs到υt的某个初等链满足①其上的正向弧均为非饱和弧。②其上的逆向弧均为非零流弧。增广链的性质：Vs到增广链上任一点也有增广链;增广链上任一点到Vt也有增广链;增广链的性质流量增广链:从υs到υt的某个初等链满足68福德－富克逊方法步骤算法的步骤：①为网络分配初始流xij标在图中弧旁的()内②寻求增广链，若不存在，则已最优,否则③在增广链上调整流量，产生新的可行流。重复②、③两步，直到最优。福德－富克逊方法步骤算法的步骤：69寻求增广链的方法寻求流量增广链的方法，是依据增广链的性质而产生的，其基本思路类似于最短树问题的生长法。从υs开始，逐个检查每个点υi，看是否存在从υs到υi的增广链。如果存在从υs到υi的增广链，而（ViVj）非饱和或（VjVi）非零流，则存在从V1到Vj的增广链。

寻求增广链的方法寻求流量增广链的方法，是依据增广链的性质而70福德－富克逊方法示例标记化算法的步骤：①为网络分配初始流xij标在图中弧旁的()内

vs101156473915vt

v5

v3

v4

v2(4)(9)(3)(1)(5)(7)(5)(8)福德－富克逊方法示例71福德－富克逊方法示例②寻求增广链从υs开始，赋上标记（－，∞），表示υs是源点，能够得到任意多的量。υs称为已标记的点。也表示增广链可以从V1延伸到V1

vs101156473915vt

v5

v3

v4

v2(4)(9)(3)(1)(5)(7)(5)(8)[-,∞]福德－富克逊方法示例②寻求增广链vs101156472福德－富克逊方法示例②寻求增广链如果vi是已经标记的点,vj是未标记的点则当(vi,vj)是非饱和弧时,vj可以标记:[vi+,ej]ej=min{ei,bij-xij}当(vj,vi)是非零流弧时,vj可以标记:[vi-,ej]ej=min{ei,xji}如果vt可以标记,则找到增广链,否则继续.如果对于一切未标记的点,均不能再标记,则已经是最优.福德－富克逊方法示例②寻求73福德－富克逊方法示例②寻求增广链如图v1是已经标记的点,其它点是未标记的点(v1,v2)是非饱和弧,v2可以标记:[v1+,e2]

e2=min{e1,b12-x12}(v1,v3)是饱和弧,目前v3和其它点暂时不能标记，即暂时没有从v1到v3或其它点的增广链。

vs101156473915vt

v5

v3

v4

v2(4)(9)(3)(1)(5)(7)(5)(8)[-,∞][vs+,11]福德－富克逊方法示例74福德－富克逊方法示例②寻求增广链如图v2是已经标记的点,v3是未标记的点(v3,v2)是非零流弧,v3可以标记:[v2-,e3]e3=min{e2,x32}=min{11,3}[-,∞][vs+,11][v2-,3][v2+,4][v3+,3][v5+,4]

vs1154315vt

v5

v3

v4

v2(4)(9)(1)(5)(7)(5)(8)1079(3)6福德－富克逊方法示例75福德－富克逊方法示例③在增广链上调整流量。vt已经标记,找到流量增广链。

vs101156473915vt

v5

v3

v4

v2(4)(9)(3)(1)(5)(7)(5)(8)[-,∞][vs+,11][v2-,3][v2+,4][v3+,3][v5+,4]正向流流量增加et，逆向流流量减少et

调整后流量f=17福德－富克逊方法示例76福德－富克逊方法示例②寻求增广链

vs101154315vt

v5

v3

v4

v2(8)(9)(3)(1)(5)(7)(9)(8)(4)967[-,∞][vs+,7][v2-,3][v3+,1][v3+,3][v4+,3]vt已经标记,找到流量增广链。福德－富克逊方法示例77福德－富克逊方法示例③在增广链上调整流量。正向流流量增加et=3，逆向流流量减少et调整后流量f=20

vs101154315vt

v5

v3

v4

v2(11)(9)(4)(5)(7)(9)(11)(4)967福德－富克逊方法示例78福德－富克逊方法示例②寻求增广链Vsv2已经标记，其余点不能标记，已经最优最大流量fmax=20

vs101154315vt

v5

v3

v4

v2(11)(9)(4)(5)(7)(9)(11)(4)967[-,∞][vs+,4]福德－富克逊方法示例79福德－富克逊方法图示算法原理图示初始流初始流福德－富克逊方法图示80图与网络理论作业作业P2185-25-4图与网络理论作业作业81运筹学第五章图与网络理论

交大管理学院杨民助运筹学第五章图与网络理论82图与网络理论图的概念网络概念网络最短树问题网络最短路问题网络最大流问题图与网络理论图的概念83图的概念什么是图图的概念

所谓图，就是顶点和边的集合，点的集合记为V，边的集合记为E，则图可以表示为：G＝（V，E），点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两个端点。在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。

图的概念什么是图图的概念84图的概念图的表示

e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念图的表示e1e2e3e485图的概念点与边

顶点数集合V中元素的个数，记作p(G)。

边数集合E中元素的个数，记作q(G)。若e=[u,v]∈E，则称u和v为e的端点，而称e为u和v的关联边，也称u，v与边e相关联。例如图5－1中的图G，p(G)=6，q(G)=9，v1，v2是e1和e2的端点，e1和e2都是v1和v2的关联边。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念点与边顶点数集合V中元素的个数，记作p(G86图的概念点边关系若点u和v与同一条边相关联，则u和v为相邻点；若两条边ei和ej有同一个端点，则称ei与ej为相邻边。例如在图5－1中v1和v2为相邻点，v1和v5不相邻；e1与e5为相邻边，e1和e7不相邻。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念点边关系若点u和v与同一条边相关联，则u和v为相87图的概念简单图若一条边的两个端点是同一个顶点，则称该边为环；又若两上端点之间有多于一条边，则称为多重边或平行边。例如图5－1的e8为环，e1，e2为两重边，e4，e5也是两重边。含有多重边的图称作多重图。无环也无多重边的图称作简单图。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念简单图若一条边的两个端点是同一个顶点，则称该边为88图的概念图的次次点v作为边的端点的次数，记作d(v)，如图5－1中，d(v1)=5,d(v4)=6等端点次为奇数的点称作奇点；次为偶数的点称作偶点。次为1的点称为悬挂点，与悬挂点连接的边称作悬挂边；次为0的点称为孤立点。图5－1中的点v5即为悬挂点，边e9即为悬挂边，而点v6则是弧立点。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念图的次次点v作为边的端点的次数，记作d(v)89图的概念定理1若图G中所有点都是孤立点，则称图G为空图。定理1所有顶点的次的和，等于所有边数的2倍。即e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念定理1若图G中所有点都是孤立点，则称图G为空图90图的概念定理2

定理2在任一图中，奇点的个数必为偶数。设V1和V2分别是图G中次数为奇数和偶数的顶点集合。由定理1有e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念定理2定理2在任一图中，奇点的个数必为偶数91图的概念链

由两两相邻的点及其相关联的边构成的点边序列称为链。v0称为链的起点，vn称为链的终点。若v0≠vn则称该链为开链，反之称为闭链或回路。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念链由两两相邻的点及其相关联的边构成的点边序列称92图的概念简单链

若链中所含的边均不相同，则称为简单链；若点均不相同，则称为初等链或通路。除起点和终点外点均不相同的闭链，称为初等回路或称为圈。例如图中e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9是一条链，且是开链，也是简单链，但不是初等链，因为v1出现两次。图的概念简单链若链中所含的边均不相同，则称为简单链；若93图的概念圈

若链中所含的边均不相同，则称为简单链；若点均不相同，则称为初等链或通路。除起点和终点外点均不相同的闭链，称为初等回路或称为圈。例如图中e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9是一个圈。图的概念圈若链中所含的边均不相同，则称为简单链；若点均94图的概念连通性

若一个图G的任意两点之间均至少有一条通路（初等链）连接起来，则称这个图G是一个连通图，否则称作不连通图。例如图中，v1和v6之间没有通路，因此它不是连通图，而如果去掉v6，则构成一个连通图。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念连通性若一个图G的任意两点之间均至少有一条通路95图的概念连通的意义

连通是一个很重要的概念，如果一个问题所对应的图是一个不连通图，则该问题一定可以分解成互不相关的子问题来加以研究，即可以把不连通图分解成连通的子图来研究。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念连通的意义连通是一个很重要的概念，如果一个问题96图的概念子图子图的定义设，G1=(V1,E1),

G2=(V2,E2)，如果V1V2，又E1E2，则称G1是G2的子图。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9e1e2e3e4e5v2v3v1必须指出，并不是从图G2中任选一些顶点和边在一起就组成G2的子图G1，而只有在G2中的一条边以及连接该边的两个端点均选入G1时，G1才是G2的子图。图的概念子图子图的定义设，G1=(V1,E1)97图的概念特殊子图当G1中不包含G2中所有的顶点和边，则称G1是G2的真子图。部分图若V1=V2，E1E2，则称G1为G2的一个部分图。若V1V2，E1={[u,v]|u∈V1,v∈V1}，则称G1是G2中由V1导出的导出子图。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9e1e2e3e4e5v2v3v1图的概念特殊子图当G1中不包含G2中所有的顶点和边，则98图的概念有向图在有些图中，边是没有方向的，即[u,v]=[v,u]，这种图称为无向图。而有些关系是不对称的，例如父子关系、上下级关系、加工工序的先后顺序等都具有单向性，用图来表示这些关系时，得到的边是具有方向的，用带箭头的线来表示，称为弧。从顶点u指向υ的弧a，记作＝a=(u,v),(u,v)≠(v,u)，其中u称为a的起点，v称为a的终点，这样的图称为有向图。仍以V表示点的集合，以A表示弧的集合，则有向图表示为D＝（V，A）图的概念有向图在有些图中，边是没有方向的，即[u,v]=99图的概念有向图例e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念有向图例e1e2e3e4100图的概念有向图的链路有向图中，在不考虑边的方向时，也可以相同地定义链，若有向图D＝（V，A）中，P是一个从u到v的链，且对P中每一条弧而言，在序列中位于该弧前面的点恰好是其起点，而位于该弧后面的点恰好是其终点，这个链P就称为是D中从u到v的一条路。当路的起点与终点相同，即u=v时，称作一条回路。顶点全不相同的路称为初等路。除起点和终点外点均不相同的回路称为初等回路。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9图的概念有向图的链路有向图中，在不考虑边的方向时，也可101图的概念树一个没有圈的图称为一个无圈图或称为林。一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。定理以下关于树的六种不同描述是等价的：①无圈连通图。②无圈，q=p-1。③连通，q=p-1。④无圈，但若任意增加一条边，则可得到一个且仅一个圈。⑤连通，但若任意舍弃一条边，图便不连通。⑥每一对顶点之间有一条且仅有一条链。图的概念树一个没有圈的图称为一个无圈图或称为林。102图的概念部分树若T是图G＝（V，E）的部分图，且T是树，则称T为G的部分树。若T是图G的部分树，则从G中去掉T中所有的边，所得到的子图称为G中的T的余树，也称为G的一个余树。余数不一定是树！一个没有圈的图称为一个无圈图或称为林。一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。图的概念部分树若T是图G＝（V，E）的部分图，且T是树103网络概念图只能用来研究事物之间有没有某种关系，而不能研究这种关系的强弱程度。网络赋权的图权程度的度量，数量描述。

v1139538362v6

v5

v3

v4

v2网络概念图只能用来研究事物之间有没有某种关系，而不能研究这种104网络最短树问题最短树问题的一般提法是：选取网络中的部分图，使得网络连通，且使总权数最短。在实际应用中，经常碰到需要求一个赋权连通图的最短树的问题。例如，用节点表示城市，用边表示可以在两个城市之间架设光缆，边上的权表示光缆的长度，试求应如何架设光缆，才能使任意两城市之间均由光缆相通，且使光缆的总长度最短。求最短树的方法，依据的是树的特点，即无圈和连通，加上最短的要求，方法主要有两种：一种称为破圈法，一种称为生长法网络最短树问题最短树问题的一般提法是：选取网络中的部分图105树的概念回顾一个没有圈的图称为一个无圈图或称为林。一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。定理以下关于树的六种不同描述是等价的：①无圈连通图。②无圈，q=p-1。③连通，q=p-1。④无圈，但增加一条边，则可得到一个且仅有一个圈。⑤连通，但若舍弃一条边，图便不连通。⑥每一对顶点之间有一条且仅有一条链。树的概念回顾一个没有圈的图称为一个无圈图或称为林。106网络最短树破圈法原理方法原理如果网络图中无圈并且q=p-1，则已经是树；如果网络图中有圈，则截去该圈中权数最大的边；这样，并不影响网络图的连通性，且能使边数减少一个；经过一定次数的截边，网络图中将再也没有圈，成为无圈图；如果此时的网络满足q=p-1，则已经是树；由于每次截去的边在圈中具有最大的权数，因此获得的树也是最短的树。网络最短树破圈法原理107

v1139538362v6

v5

v3

v4

v2网络最短树破圈法方法步骤①在网络图中寻找一个圈，若已经无圈则转③。②在圈中选取权数最大的边，从网络图中截去该边，对新的网络，转①。③若q=p-1，则已找到最短树，否则网络图不连通，无最短树。方法示例：例5－4对图中的网络，用破圈法求最短树。

v1139538362v6v5v3v108网络最短树生长法原理

方法原理类似于自然界中植物生长的过程，结合就近生长和避免构成圈的要求，逐步生长直到所有的点都已经被包含。如果原网络不连通，则在生长过程中会出现某些点不能被生长，则结束。避圈的原理是已经被包含在生长过的树中的点不再被生长。由于在每次生长时都采用就近生长的方法，生成的树一定是最短树。网络最短树生长法原理109

v1139538362v6

v5

v3

v4

v2网络最短树生长法1方法步骤①从图上任选一点υi，令②从Sk中的各点到Sk中各点的边中选权数最小的边，设为[υi，υj]，则若这样的边不存在，则原图没有最短部分树。③令若S=V，则已找到最短树，否则②，v1139538362v6v5v3v110

v1139538362v6

v5

v3

v4

v2网络最短树生长法2方法示例取S={v1},则S到其余点的距离在距离矩阵中第一行v2v3v4v5v6S126∞∞∞V2389∞S2389∞v1139538362v6v5v3v111网络最短树生长法3方法示例v2v3v4v5v6S126∞∞∞V2389∞S2389∞V353∞S353∞V5∞1S451V63S53网络最短树生长法3方法示例v2v3v4v5v6S126112网络最短树生长法4v2v3v4v5v6S126∞∞∞V2389∞S2389∞V353∞S353∞V5∞1S451V63S53

v1139538362v6

v5

v3

v4

v2网络最短树生长法4v2v3v4v5v6S126∞∞∞V113网络最短路线问题最短路线问题的一般提法是：欲寻找网络中从起点υ1到终点υn的最短路线，即寻求连接这两点的边的总长度为最小的通路，最短路线中的网络大都是有向网络，也可以是无向网络。adbetcfs9757845646547图4-7网络最短路线问题最短路线问题的一般提法是：欲寻找网络中从114最短路问题的狄克斯拉算法把V分成两个集合令计算求若vk=vn则已经求得vn到v1的最短路线，否则继续计算使用条件lij≥0最短路问题的狄克斯拉算法把V分成两个集合令计算求若vk=v115算法解释若以p(vi)记v1到vi的最短距离，则根据动态规划原理应有第一步取P(v1)＝0，而T(vj)则是对P(vj)所取的初值；

v1139538362v6

v5

v3

v4

v2狄克斯拉算法1算法解释第一步取P(v1)＝0，而T(vj)则是对P(v116狄克斯拉算法2算法解释第二步利用P(vi)已知，据上式对T(vj)进行修正；

v1139538362v6

v5

v3

v4

v2狄克斯拉算法2算法解释第二步利用P(vi)已知，据上117狄克斯拉算法3算法解释第三步对T(vj)求

v1139538362v6

v5

v3

v4

v2狄克斯拉算法3算法解释第三步对T(vj)求v11118狄克斯拉算法4算法解释k=2,不是最优，继续

v1139538362v6

v5

v3

v4

v2狄克斯拉算法4算法解释k=2,不是最优，继续v11119狄克斯拉算法5算法解释在所有的T(vj)中确定最小的

v1139538362v6

v5

v3

v4

v2狄克斯拉算法5算法解释在所有的T(vj)中确定最小的120狄克斯拉算法6算法解释k=3,不是最优，继续

v1139538362v6

v5

v3

v4

v2狄克斯拉算法6算法解释k=3,不是最优，继续v11121狄克斯拉算法7算法解释k=5,不是最优，继续

v1139538362v6

v5

v3

v4

v2狄克斯拉算法7算法解释k=5,不是最优，继续v11122狄克斯拉算法8算法解释k=6=n,已经是最优。如果希望计算v1到v4的最短距离，继续

v1139538362v6

v5

v3

v4

v2狄克斯拉算法8算法解释k=6=n,已经是最优。如果希望计123狄克斯拉算法9表格实现vjv1v2v3v4v5v6初始值T(vj

)0∞∞∞∞∞

v1139538362v6

v5

v3

v4

v2第一次P()+lij0+20+60+∞0+∞0+∞T()26∞∞∞狄克斯拉算法9表格实现vjv1v2v3v4v5v6初始值T124狄克斯拉算法10表格实现vjv1v2v3v4v5v6初始值T(vj

)0∞∞∞∞∞第一次P()+lij0+20+60+∞0+∞0+∞T()26∞∞∞第二次P()+lij2+32+82+92+∞T()51011∞第三次P()+lij5+55+35+∞T()108∞第四次P()+lij8+∞8+1T()109狄克斯拉算法10表格实现vjv1v2v3v4v5v6初始值125福德算法1适用于有负权，但无负回路的有向或无向网络，其算法步骤如下：

令计算若对所有j则最优，否则把k的值加1，继续计算。若k=n-1，则说明存在负回路，最短路线不存在。福德算法1适用于有负权，但无负回路的有向或无向网络，其算法126福德算法2适用于有负权，但无负回路的有向或无向网络，算法中dj(k)为从υ1到υj的边数不超过k的路线中距离最短的。算