运筹学图与网络问题课件.ppt

1、图与网络问题o1、引例、引例o一群人之间存在错综的关系：赵、钱、孙、一群人之间存在错综的关系：赵、钱、孙、李、周。赵与钱相互认识、与孙也相互认李、周。赵与钱相互认识、与孙也相互认识；钱与孙相互认识、孙与李相互认识。识；钱与孙相互认识、孙与李相互认识。他们与周都不认识。他们与周都不认识。o如何清晰的表示这些人之间的关系呢？如何清晰的表示这些人之间的关系呢？o当人数更多、人们间相互关系更复杂时，当人数更多、人们间相互关系更复杂时，该怎样描述人们间的关系？该怎样描述人们间的关系？图与网络问题图与网络问题图与网络问题图与网络问题o2、相关概念o（1）点、边、弧o（2）无向图、有向图o（3）链、圈、连通

2、图o（4）路、回路o（5）权、网络图与网络问题o点用于表示各种事物，一般用V表示 一个图中往往有多个点，一般用v1、v2、表示。一个图中所有的n个点构成点集V=v1、v2、vno边用于描述事物间关系的线，一般用E表示。一个图中往往有多个边，一般用e1、e2、表示。一个图中所有的n条边构成边集E=e1、e2、eno弧带有箭头的线，一般用A表示。一个图中的n条弧，一般用a1、a2、表示。一个图中所有的n条边构成边集A=a1、a2、an图与网络问题o无向图：由点和边构成的图，简称“图”，一般用G表示。G=（V，E），V是图G的点集，E是图G的边集。o有向图：由点和弧构成的图，一般用D表示。D=（V，

3、A），V是图D的点集，A是图D的弧集。图与网络问题o链：对于无向图无向图G来说，如果存在一个点、边交错序列（v1、e1、v2、e2、vn）,其中边ei的起点是vi，终点是vi+1，即ei=（vi，vi+1），则称这条点、边交错序列为联结v1，vn的链。o圈：如果一条链（v1、e1、v2、e2、vn）中， v1=vn，则称之为圈o连通图：o对一个无向图G，若任何两个不同的点之间，至少存在一条链，则称G为连通图图与网络问题o路：在有向图有向图D中，如果存在一个点、弧交错序列： （v1、a1、v2、a2、vn）,其中边ai的起点是vi，终点是vi+1，即ai=（vi，vi+1），则称这条点、弧交错序

4、列为联结v1，vn的一条路。o回路：如果路的第一个点和最后一个点相同，则称这条路为回路。图与网络问题o权：当无向图G的每一条边（vi，vj） ，或有向图D的每一条弧（vi，vj）上都相应地有一个数来进一步说明点与点之间的关系，那么这样的数我们可以称之为权，记为wij。给无向图G或有向图D添加权的过程，通常称为赋权。o网络：我们称赋了权的有向图D为网络。图与网络问题o最短路问题是对一个赋权的有向图D中的指定的两个点vs到vt找到一条从vs到vt的路，使得这条路上所有弧的权数的总和最小，这条路被称为从vs到vt的最短路，这条路上所有弧的权数的总和被称之为从vs到vt的距离。o如下图，找出从v1到v

5、4的最短路v1v2v3v442159v2图与网络问题161617171822222323303031414159vsv1v2v3v4vt图与网络问题o有向图D=（V，A），oV=v1，v2，v6oA=(v1,v2) ，(v1,v4)，(v1,v3),(v2,v6), (v4,v2), (v4,v6), (v3,v5),(v3,v5), (v5,v4), (v5,v6) ocij表示vi到vj的权v1v2v3v4v5v63252153571图与网络问题ov1到到vt的最短路步骤：的最短路步骤：o1、给起点、给起点v1标号（标号（0，s）o2、确定已标号点集、确定已标号点集I，未标号点集，未标号点

6、集J，找出弧集，找出弧集A=（vi,vj）|vi I，ovj Jo3、如果弧集、如果弧集A=空集，那么如果空集，那么如果vt已标号，则结束，如果已标号，则结束，如果vt未标号则未标号则说明不存在从说明不存在从v1到到vt的路。否则，的路。否则，如果弧集如果弧集A空集，转空集，转4o4、对、对A中的弧，计算中的弧，计算sij=li+cij,从中找出值最小的弧，给此弧标号为从中找出值最小的弧，给此弧标号为（sij，i）v1v2v3v4v5v63252153571双标号（双标号（sij，i）中）中sij表示表示由由vi到vj的最短路长，的最短路长， i表示表示vi到vj的最短路上，此点前的最短路上，

7、此点前一个点的下角标。一个点的下角标。图与网络问题v1v2v3v4v5v61510326245176v7（甲）（甲）（乙）（乙）图与网络问题o1、 永久标号：永久标号：v1（0，s）oK=1o2、I=v1，J=v2,v3,v4,v5,v6,v7，A=(v1, v2)，(v1, v3)o3、A o4 4、s s1212=l=l1 1+c+c1212=0+15=15=0+15=15o s s1313=l=l1 1+c+c1313=0+10=10=0+10=10oMinsMinsijij=s=s1313, ,永久标号：永久标号：v v3 3= =（s sijij,i,i）= =（1010，1 1）v

8、1v2v3v4v5v61510326245176v7（0，s）（10，1）图与网络问题os s1212=l=l1 1+c+c1212=0+15=15=0+15=15oK=2o2、I=v1,v3，J=v2, v4,v5,v6,v7，A=(v1, v2)，(v3, v2)，(v3, v5)o3、A o4 4、s s3232=l=l3 3+c+c3 32 2= =1010+ +3 3=1=13 3o s s3535=l=l3 3+c+c3535= =1 10+0+5 5=1=15 5oMinsMinsijij=s=s3232, ,永久标号：永久标号：v v2 2= =（s sijij,i,i）= =

9、（1313，3 3）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）图与网络问题os s3535=l=l3 3+c+c3535= =1 10+0+5 5=1=15 5oK=3o2、I=v1, v2, v3，J=v4,v5,v6,v7，A=(v2, v7)，(v2, v4)，(v3, v5)o3、A o4 4、s s2727=l=l2 2+c+c2727= =1313+ +1717= =3030o s s2424=l=l2 2+c+c2424= =1313+ +6 6=1=19 9oMinsMinsijij=s=s3535, ,永久标号：永久标号：v v5

10、 5= =（s sijij,i,i）= =（1515，3 3）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）图与网络问题os s2727=l=l2 2+c+c2727= =1313+ +1717= =3030os s2424=l=l2 2+c+c2424= =1313+ + 6 6=1=19 9oK=4o2、I=v1, v2, v3,v5，J=v4,v6,v7，A=(v2, v7)，(v2, v4)，(v5, v4), (v5, v6)o3、A o4 4、s s5454=l=l5 5+c+c5454= =1515+ +4 4= =1919o

11、 s s5656=l=l5 5+c+c5656= =1515+ +2 2=1=17 7oMinsMinsijij=s=s5656, ,永久标号：永久标号：v v6 6= =（s sijij,i,i）= =（1717，5 5）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）图与网络问题os s2727= =30 30 s s2424=1=19 9 s s5454= =1919oK=5o2、I=v1, v2, v3,v5,v6，J=v4,v7，A=(v2, v7)，(v2, v4)，(v5, v4), (v6, v7)o3、A o4

12、4、s s6767=l=l6 6+c+c6767= =1717+ +6 6= =2323oMinsMinsijij=s=s2424=s=s5454, ,o 永久标号：永久标号：v v4 4= =（s sijij,i,i）= =（1919，2 2）或或（1919，5 5）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2） /(19，5)图与网络问题os s2727= =30 30 oK=6o2、I=v1, v2, v3, v4,v5,v6，J=v7，A=(v2, v7) ，(v4, v7) ，(v6, v7)o3、A o4

13、 4、s s4747=l=l4 4+c+c4747= =1919+ +2 2= =2121os s6767=l=l6 6+c+c6767= =1717+ +6 6= =2323oMinsMinsijij=s=s4747, ,永久标号：永久标号：v v7 7= =（s sijij,i,i）= =（2121，4 4）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2） /(19，5)（21，4）图与网络问题oV V1 1到到v v7 7的最短路长为的最短路长为2121，最短路径是，最短路径是v1v2v3v4v5v6151032

14、6245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2） /(19，5)（21，4）v7v4v2v7v4v5v3v1v3v1图与网络问题o几个概念：几个概念：o树：无圈的连通图树：无圈的连通图o生成子图：给定一个无向图生成子图：给定一个无向图G=(V,E)，保留，保留G中的中的所有点，删掉部分所有点，删掉部分G的边，所得的新图的边，所得的新图G就是就是G的生成子图。的生成子图。o生成树：如果图生成树：如果图G的生成子图是一个树，则称这的生成子图是一个树，则称这个生成子图为生成树。个生成子图为生成树。o最小生成树：在一个赋权的连通的无向图中，找最小生成树：在一个赋

15、权的连通的无向图中，找出一个生成树，如果这个生成树的所有边的权数出一个生成树，如果这个生成树的所有边的权数之和最小，那么这个树就叫做最小生成树。之和最小，那么这个树就叫做最小生成树。图与网络问题o算法步骤：算法步骤：o1、在给定的赋权连通图上任找一圈、在给定的赋权连通图上任找一圈o2、在找到的圈中删掉一条权数最大的边、在找到的圈中删掉一条权数最大的边o3、如果余下的图不含圈，则它们构成最、如果余下的图不含圈，则它们构成最小生成树。小生成树。图与网络问题图与网络问题图与网络问题图与网络问题o算法步骤：算法步骤：o1、另作一图、另作一图G，绘制原图，绘制原图G的所有顶点的所有顶点o2、依次选取权数

16、最小的边、依次选取权数最小的边o3、若在图、若在图G中加入此边后不会产生圈，中加入此边后不会产生圈，则在图则在图G中加入此边。否则在剩下的边中中加入此边。否则在剩下的边中继续选取。继续选取。图与网络问题图与网络问题o给了一个带发点和收点的网络，其每条弧给了一个带发点和收点的网络，其每条弧的赋权表示容量。在不超过每条弧容量的的赋权表示容量。在不超过每条弧容量的前提下，求从发点到收点的最大流量。前提下，求从发点到收点的最大流量。图与网络问题图与网络问题图与网络问题 图与网络问题图与网络问题图与网络问题图与网络问题图与网络问题图与网络问题o最小费用最大流问题：给了一个带收发点的网络，对每一条弧（vi，vj），除了给出了容量cij外，还给出了这条弧的单位流量的费用bij，要求一个最大流F，并使得总费送费用最小。图与网络问题图与网络问题图与网络问题图与网络问题图与网络问题图与网络问题图与网络问题图与网络问题图与网络问题图与网络问题图与网络问题