图与网络分析物流运筹学

图与网络分析在物流系统中的应用(GraphTheoryandNetworkAnalysis)图与网络的基本知识最短路问题树及最小树问题BDACABCD哥尼斯堡七空桥一笔画问题应用及解决的问题•配送运输规划问题•物流车辆规划调度系统•物流园区规划一、图与网络的基本知识（一）、图与网络的基本概念EADCB1、一个图是由点和连线组成。（连线可带箭头，也可不带，前者叫弧，后者叫边）一个图是由点集和中元素的无序对的一个集合构成的二元组，记为G=(V，E)，其中V中的元素叫做顶点，V表示图G的点集合；E中的元素叫做边，E表示图G的边集合。jvV}{keEjvkeVv1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例654321,,,,,vvvvvvV},,,,,,,,{10987654321eeeeeeeeeeE，},{211vve},{212vve},{323vve},{434vve},{315vve},{536vve},{537vve},{658vve},{669vve},{6110vve图12、如果一个图是由点和边所构成的，则称其为无向图，记作G=(V，E)，连接点的边记作[vi,vj]，或者[vj,vi]。3、如果一个图是由点和弧所构成的，那么称它为有向图，记作D=(V,A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。v4v6v1v2v3v5V={v1,v2,v3,v4,v5,v6}，A={(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)}图24、一条边的两个端点是相同的,那么称为这条边是环。5、如果两个端点之间有两条以上的边，那么称为它们为多重边。6、一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。7、每一对顶点间都有边相连的无向简单图称为完全图。有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。8、以点v为端点的边的个数称为点v的度（次），记作。)(vd图中d(v1)=4，d(v6)=4（环计两度）定理1所有顶点度数之和等于所有边数的2倍。定理2在任一图中，奇点的个数必为偶数。所有顶点的入次之和等于所有顶点的出次之和。有向图中，以vi为始点的边数称为点vi的出次，用表示；以vi为终点的边数称为点vi的入次，用表示；vi点的出次和入次之和就是该点的次。)(ivd)(ivd9、设G1=（V1,E1），G2=（V2,E2）如果V2V1,E2E1称G2是G1的子图；如果V2=V1,E2E1称G2是G1的部分图或支撑子图。v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图在实际应用中，给定一个图G=（V，E）或有向图D=（V，A），在V中指定两个点，一个称为始点（或发点），记作v1，一个称为终点（或收点），记作vn，其余的点称为中间点。对每一条弧，对应一个数，称为弧上的“权”。通常把这种赋权的图称为网络。Avvji),(jiw10、由两两相邻的点及其相关联的边构成的点边序列称为链。如:v0，e1，v1，e2，v2，e3，v3,…,vn-1,en，vn，记作（v0，v1，v2，v3,…,vn-1，vn），e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e1011、图中任意两点之间均至少有一条通路，则称此图为连通图，否则称为不连通图。其链长为n，其中v0，vn分别称为链的起点和终点。若链中所含的边均不相同，则称此链为简单链；所含的点均不相同的链称为初等链,也称通路。（二）、图的矩阵表示对于网络（赋权图）G=（V，E），其中边有权，构造矩阵，其中：称矩阵A为网络G的权矩阵。),(jivvjiwEvvEvvwajijijiji),(0),(nnjiaA)(nnjiaA)(EvvEvvajijiji),(0),(1设图G=（V，E）中顶点的个数为n，构造一个矩阵，其中：称矩阵A为网络G的邻接矩阵。654321654321010101101001010111101010001101111010vvvvvvvvvvvvB例权矩阵为：邻接矩阵为：v5v1v2v3v4v64332256437654321654321030303302004020576305020007204346040vvvvvvvvvvvvA问题•图（顶点、边）、有限图、无限图•无向图、有向图、环、多重边•多重图、简单图、完全图、有向完全图、二部图•顶点的次、出次、入次、悬挂点、孤立点、奇点、偶点•子图、生成子图（支撑图）、网络（赋权图）•链、初等链、圈、初等圈、回路、连通图•图的矩阵表示、邻接矩阵•欧拉道路、欧拉回路、中国邮路问题树的概念•树、树叶、分枝点•数的性质•生成子图、生成树、树枝、弦•最小生成树•避圈法、破圈法•有向树、根树、叶、分枝点、叉树二、树及最小树问题已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。v1v2v3v4v5v61、一个连通的无圈的无向图叫做树。树中次为1的点称为树叶，次大于1的点称为分支点。树的性质：（1）树必连通，但无回路（圈）。（2）n个顶点的树必有n-1条边。（3）树中任意两个顶点之间，恰有且仅有一条链（初等链）。（4）树连通，但去掉任一条边，必变为不连通。（5）树无回路（圈），但不相邻的两个点之间加一条边，恰得到一个回路（圈）。v1v2v3v4v5v62、设图是图G=(V,E)的一支撑子图，如果图是一个树,那么称K是G的一个生成树（支撑树），或简称为图G的树。图G中属于生成树的边称为树枝，不在生成树中的边称为弦。),(1EVK一个图G有生成树的充要条件是G是连通图。v1v2v3v4v5v1v2v3v4v5),(1EVK用避圈法求出下图的一个生成树。v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8（一）破圈法（二）避圈法在图中任取一条边e1，找一条与e1不构成圈的边e2，再找一条与{e1，e2}不构成圈的边e3。一般设已有{e1，e2，…，ek}，找一条与{e1，e2，…，ek}中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止。v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v53、最小生成树问题如果图是图G的一个生成树，那么称E1上所有边的权的和为生成树T的权，记作S(T)。如果图G的生成树T*的权S(T*)，在G的所有生成树T中的权最小，即那么称T*是G的最小生成树。),(1EVT)(min)(*TSTST某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。v1v2v3v4v5v66515723445v1v2v3v4v5v612344v1v2v3v4v514231352最短路的一般提法为：设为连通图，图中各边有权（表示之间没有边），为图中任意两点，求一条路，使它为从到的所有路中总权最短。即：最小。),(EVGjiljiltsvv,sv),(jivvjivv,tv),()(jivvjilL(一)、狄克斯屈拉(Dijkstra)算法适用于wij≥0，给出了从vs到任意一个点vj的最短路。三、最短路问题算法步骤：1.给始点vs以P标号，这表示从vs到vs的最短距离为0，其余节点均给T标号，。2.设节点vi为刚得到P标号的点，考虑点vj，其中，且vj为T标号。对vj的T标号进行如下修改：3.比较所有具有T标号的节点，把最小者改为P标号，即：当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。0)(svP),,3,2()(nivPiEvvji),(])(,)(min[)(jiijjlvPvTvT)](min[)(ikvTvP例一、用Dijkstra算法求下图从v1到v6的最短路。v1v2v3v4v6v5352242421解（1）首先给v1以P标号，给其余所有点T标号。0)(1vP)6,,3,2()(ivTi（2）（3）3]30,min[])(,)(min[)(12122lvPvTvT5]50,min[])(,)(min[)(13133lvPvTvT3)(2vP（4）4]13,5min[])(,)(min[)(23233lvPvTvT5]23,min[])(,)(min[)(24244lvPvTvT5]23,min[])(,)(min[)(25255lvPvTvTv1v2v3v4v6v53522424214)(3vP（5）（6）8]44,6min[])(,)(min[)(35355lvPvTvT5)(4vP5)(5vP9]45,min[])(,)(min[)(46466lvPvTvT7]25,min[])(,)(min[)(56566lvPvTvT7)(6vP（7）（8）（9）（10）反向追踪得v1到v6的最短路为：6521vvvv237184566134105275934682求从1到8的最短路径237184566134105275934682X={1},w1=0min{c12,c14,c16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0237184566134105275934682X={1,4}min{c12,c16,c42,c47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},p2=2p1=0p4=1p2=2237184566134105275934682X={1,2,4}min{c13,c23,c25,c47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},p6=3p2=2p4=1p1=0p6=3237184566134105275934682X={1,2,4,6}min{c23,c25,c47,c67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},p7=3p2=2p4=1p1=0p6=3p7=3237184566134105275934682X={1,2,4,6,7}min{c23,c25,c75,c78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6237184566134105275934682X={1,2,4,6,7}min{c23,c53,c58,c78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8X={1,2,3,4,5,6,7},p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8237184566134105275934682X={1,2,3,4,6,7}min{c38,c58,c78}=min{8+6,6+4,3+7}=min{14,10,11}=10X={1,2,3,4,5,6,7