《运筹学》第六章 图与网络分析

图与网络分析(GraphTheoryandNetworkAnalysis)图与网络的基本知识最短路问题中国邮路问题最大流问题BDACABCD哥尼斯堡七桥问题一笔画问题引论图的用处•A、B、C、D、E某公司的五支球队进行循环赛组织机构设置图ABCDE总公司分公司工厂或办事处一、图与网络的基本知识（一）图与网络的基本概念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)}图25、如果两个端点之间有两条以上的边，称为多重边。6、一个无环、无多重边的图称为简单图，含有多重边的图称为多重图。7、无向完全图——每一对顶点间都有边相连的简单图；有向完全图——指每一对顶点之间有且仅有一条有向边的简单图。4、一条边的两个端点是相同的,称此边为环。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10次为零的点——弧立点8、以点v为端点的边的个数称为点v的次，记作)(vd图中d(v1)=4，d(v6)=4（环计两次）次为偶数的点——偶点次为1的点——悬挂点悬挂点的关联边——悬挂边次为奇数的点——奇点·v7定理1任何图中，顶点次数的总和等于边数的2倍。所有顶点的入次之和等于所有顶点的出次之和。有向图中：以vi为始点的边数称为点vi的出次，用表示；以vi为终点的边数称为点vi的入次，用表示；vi点的出次和入次之和就是该点的次。)(ivd)(ivd定理2在任一图中，奇点的个数必为偶数。一个称为始点（或发点），记作v1，一个称为终点（或收点），记作vn，其余的点称为中间点。Avvji),(jiw9、在实际应用中，给定一个图G=（V，E）或有向图D=（V，A），在V中指定两个点:对每一条弧，对应一个数，称为弧上的“权”。通常把这种赋权的图称为网络。e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e1011、图中任意两点之间均至少有一条通路，则称此图为连通图，否则称为不连通图。若链中所含的边均不相同，称为简单链所含的点均不相同的链称为初等链,也称通路。10、由两两相邻的点及其相关联的边构成的点边序列称为链。),,1)(,(),,,,,,,(112110ktvvevevevevtttkkkiiiiiiiiii，且。分别为链的起点和终点、，链长为kiivvk0对于网络（赋权图）G=（V，E），其中边有权，构造矩阵，其中：),(jivvjiwEvvEvvwajijijiji),(0),(nnjiaA)(EvvEvvajijiji),(0),(1nnjiaA)(设图G=（V，E）中顶点的个数为n，构造一个矩阵，其中：（二）图的矩阵表示称矩阵A为网络G的权矩阵称矩阵A为网络G的邻接矩阵654321654321010101101001010111101010001101111010vvvvvvvvvvvvB例权矩阵邻接矩阵v5v1v2v3v4v64332256437654321654321030303302004020576305020007204346040vvvvvvvvvvvvA二、中国邮递员问题一、欧拉回路与道路定义连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。推论一个多重连通图G有欧拉道路的充分必要条件是G有且仅有两个奇点。具有欧拉回路的图称为欧拉图。定理一个多重连通图G是欧拉图的充分必要条件是G中无奇点。一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？图论语言描述：给定一个连通图G，每边有非负权l(e)，要求一条回路过每边至少一次，且满足总权最小。二、中国邮路问题中国邮路问题可转化为如下问题：在连通图G=(V,E)中，求一个边集E1∈E，把G中属于E1的边均变为两重边得到图G*=G+E1，使其满足G*无奇点，且最小。∑1∈1)(=)(EeelEL奇偶点图上作业法（1）每条边最多重复一次；（2）对图G中每个初等圈来讲，重复边的长度和不超过圈长的一半。定理：已知图G*=G+E1无奇点，则∑1∈1)(=)(EeelEL最小的充分必要条件为：（1）找出图G中的所有的奇顶点，把它们两两配成对，而每对奇点之间必有一条通路，把这条通路上的所有边作为重复边追加到图中去，这样得到的新连通图必无奇点。（2）如果边e=（u,v）上的重复边多于一条，则可从重复边中去掉偶数条，使得其重复边至多为一条，图中的顶点仍全部都是偶顶点。（3）检查图中的每一个圈，如果每一个圈的重复边的总长不大于该圈总长的一半，则已经求得最优方案。如果存在一个圈，重复边的总长大于该圈总长的一半时，则将这个圈中的重复边去掉，再将该圈中原来没有重复边的各边加上重复边，其它各圈的边不变，返回步骤（2）。奇偶点图上作业法判定标准1:在最优邮递路线上，图中的每一条边至多有一条重复边。判定标准2:在最优邮递路线上，图中每一个圈的重复边总权小于或等于该圈总权的一半。例：求解下图所示网络的中国邮路问题，图中数字为该边的长。v1v2v3v4v5v6v7v8v9243449556434v1v2v3v4v5v6v7v8v9243449643455v1v2v3v4v5v6v7v8v9243449556434v1v2v3v4v5v6v7v8v9243449556434v1v2v3v4v5v6v7v8v9243449556434l12+2l23+2l36+l89+2l78+l69+l14+2l47=51v1v2v3v4v5v6v7v8v9243449556434最短路的一般提法为：设为连通图，图中各边有权（表示之间没有边），为图中任意两点，求一条路，使它为从到的所有路中总权最短。即：最小。),(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）544535355],min[]l)v(P,)v(Tmin[)v(T5)(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{c16,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,5,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,5,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,8},p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134105275934682X={1,2,3,4,5,6,7,8}1到8的最短路径为{1，4，7，5，8}，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10例：5年内，哪些年初购置新设备，使5年内的总费用最小。解：（1