图与网络-西安电子科技大学经济管理学院

1运筹学图与网络分析第十章图与网络赵玮3主要内容：10.1基本概念10.2最短路问题（一）Bellman最优化原理（二）Dijustra算法（双括号法）（三）通信线路布施问题（四）设备更新问题10.3最小生成树（一）基本概念与理论（二）Kruskal算法（加边法、破圈法）（三）丢边法（破圈法）4主要内容：10.4最大流问题（一）基本概念（二）双标号算法10.5最小费用最大流（一）基本概念（二）求解算法5§10.1基本概念1图def1：一个无向图（简称为图）G是一个有序的二元组，记为G=(V,E)。其中V={V1…Vn}称为G的点集合，E=(eij)称为G的边集合，evj为连接VV与Vj的边。6若N和E均为有限集合，则称为G为有限图，否则称无限图。若G中既没有有限回路（圈），也没有两条边连接同一对点，则称G为简单图。如右图之（a），右图之（b）不是简单图。若G为简单图，且G中每个点对之间均有一条边相连，则称G为完全图。如图（a）是简单图，但不是完全图。图a图b7def2：一个有向图G是一个有序的二元组，记为G=(V,A)，其中V=(V1V2…Vn)称为G的点集合，A={aij}称为G的弧（有向边）集合，aij是以Vi指向Vj的一条弧。|V|=n表示G中节点个数为n，此节点个数n也称为图G的阶|A|=m表示有向图G中弧的个数为m任一顶点相关联（连接）的边的数目称为该顶点的次数82连通图def3：在有向图G中,一个点和边的交替序列{VieijVj…VkeklVl}称为G中从点Vi到Vl的一条路，记为A，其中Vi为此路A的起点，Vj为路A的终点；若路A的起点与终点重合,则称A为回路；又若G中点Vi与Vj间存在一条路，则称点Vi与Vj是连通的；若G中任何二点都是连通的，则称G为连通图，或图G为连通的。在无向图中有对应的概念。有向图路回路无向图链圈93子图def4：设有两个图：G1=(V1,E1)，G2=(V2,E2)若有，则称G1为G2的子图，记作；若有V1=V2而,则称图G1=(V1,E1)是图G2=(V2,E2)的生成子图（支撑子图）。21VV21EE21GG21EE10例：下示图G1是图G的子图，图G2是图G的生成子图。V1V3V2V4V1V2V4V1V3V2V4（a）图G（b）图G1（c）图G2114赋权图（加权图）与网路def5：设G是一个图（或有向图），若对G的每一条边（或弧）eij都赋予一实数ωij，称其为该边（弧）的权，则G连同其他弧上的权集合称为一个赋权图，记作G=(V,E,W)或G=(V,A,W)，此中W={ωij}，ωij为对应边（弧）eij的权。若G=(V,E,W)（或(V,A,W)）为赋权图，且在G的V中指定一个发点（常记为Vs）和一个收点（记为Vt），其余点称为中间点，则称这样指定了发点与收点的赋权图G为网络。12§10.2最短路问题def6：设G=（V,A,W）为一个赋权有向图，Vs为指定发点，Vt为指定收点，其余为中间点，P为G中以Vs到Vt的一条有向路，则称为路P的长度，若有则称为G中从Vs到Vt的最短路，为该最短路的长度（此中F为G中所有从Vs到Vt的全体有向路的集合）。PaaWdefPW)()()(min)~(PWPWFPP~)P~W(13最短路问题在企业厂址上选择，厂址布局，设备更新，网络线路安装等工程设计与企业管理中有重要应用。14（一）Bellman最优化原理1命题1：若P是网络G中从Vs到Vt的一条最小路，Vl是P中除Vs与Vt外的任何一个中间点，则沿P从Vs到Vl的一条路P1亦必是Vs到Vl的最小路。VsV1VlV2VtP2P115证明（反证）：若P1不是从Vs到Vl的最小路，则存在另一条Vs到Vl的路P2使W(P2)W(P1)，若记路P中从Vl到Vt的路为P3。则有W(P2)+W(P3)W(P1)+W(P3)=W(P)，此说明G中存在一条从Vs沿P2到Vl沿P3再到Vt的更小的一条路，这与P使G中从Vs到Vt的一条最小路矛盾。162算法思想：设G中从Vs到Vt的最小路P：Vs…Vj…Vk…Vt，则由上述命题知：P不仅是从Vs到Vt的最小路，而且从Vs到P中任意中间点的最短路也在P上，为此可采用如下求解思路：⑴为求得Vs到Vt的最短路，可先求得Vs到中间点的最短路，然后由中间点再逐步过渡到终点Vt。17⑵在计算过程中，需要把V中“经判断为最短路P途径之点i”和“尚未判断是否为最短路P途径之点j”区分开来，可设置集合I和J,前者归入I，后者归入J，并令算法初始时，I中仅包含Vs，其他点全在J中，然后随着求解过程的进行，I中的点逐渐增加（相应J中的点逐渐减少），直到终点Vt归入I（相应J=φ），此时迭代结束。I称为已标号集合,J称为未标号集合。18⑶为区分中间点Vk是否已归入I中以及逆向求解最短路的方便，可在归入I中的点Vj上方给予双标号（lj,Vk），此中lj表示从Vs到Vj最短路的距离，而Vk则为从Vs到Vj最短路P中Vj的前一途径点。⑷为在计算机上实现上述求解思想，还需引入G中各点间一步可达距离阵D=(dij)n×n，此中|V|=njijiwdijij不能一步到达，能一步到达，19⑸以下介绍的是适用于弧权为正值的有向网络中求最短有向路的Dijkstra算法，又称双括号法。事实上该算法亦适用于弧权为负值的有向网络求最短路问题。20由图G建立一步可达距离阵D=(dij)n×n给V1(Vs)括号(l1,Vk)=(0,s)给出已标号集合I和未标号集合J的元素对于给定的I和J，确定集合A={aij|Vi∈I，Vj∈J}计算距离给Vk括号(lk,Vh)lk=lh+WhkI=I+{Vk}J=J–{Vk}A=φ或J＝φ从Vt逆向搜索双括号，可得最小路P途径各点及最小路距离ENDhkhijIiiWlJWl}V|min{jNY（二）Dijkstra算法（双括号法）图一21例1（教材208页）求G的最短路，图G形如下形。解：利用上述Dijkstra算法步骤可得表一所示求解过程，并有最短路P：V6V4V3V1，最短距离|P|=2+1+5=8。512图（一）22已标号点Vj双标号(lj,Vk)IJA={aij|Vi∈I,Vj∈J}hkhijIiiWlJWl}V|min{jV1(0,s)V1V2~V6{a12,a13,a14}min{l1+W12,l1+W13,l1+W14}=min{0+3,0+2,0+5}=2=l1+W13V3(2,V1)V1,V3V2,V4V5,V6{a12,a14,a34}min{l1+W12,l1+W13,l3+W34}=min{0+3,0+5,2+1}=3=l1+W12,l3+W34V2V4(3,V1)(3,V3)V1~V4V5,V6{a26,a46}min{l2+W26,l4+W46}=min{3+7,3+5}=8=l4+W46V6(8,V4)V1~V4,V6V5φEND表一（例1求解过程）23例2求如下G之最小路V1V4V2V6V8V5V7333V36666117图二74224dijV1V2V3V4V5V6V7V8V10263∞∞∞∞V2∞03∞∞7∞∞V3∞∞0137∞∞V4∞∞∞06∞∞∞V5∞∞∞∞016∞V6∞∞∞∞∞0∞4V7∞∞∞∞∞∞06V8∞∞∞∞∞∞∞0解表二25表三（例2求解过程）已标号点Vj双标号(lj,Vk)IJA={aij|Vi∈I,Vj∈J}hkhijIiiWlJWl}V|min{jV1(0,s)V1V2~V8{a12,a13,a14}min{l1+W12,l1+W13,l1+W14}=min{0+2,0+6,0+3}=2=l1+W12V2(2,V1)V1,V2V3~V8{a13,a14,a23,a26}min{l1+W13,l1+W14,l2+W23,l2+W26}=min{0+6,0+3,2+3,2+7}=3=l1+W14V4(3,V1)V1,V2,V4V3,V5~V8{a13,a23,a26,a45}min{l1+W13,l2+W23,l2+W26,l4+W45}=min{0+6,2+3,2+7,3+6}=5=l2+W23V3(5,V2)V1~V4V5~V8{a26,a35,a36,a45}min{l2+W26,l3+W35,l3+W36,l4+W45}=min{2+7,5+3,5+7,3+6}=8=l3+W35V5(8,V3)V1~V5V6V7V8{a26,a36,a56,a57}min{l2+W26,l3+W36,l5+W56,l5+W57}=min{2+7,5+7,8+1,8+6}=9=l2+W26,l5+W56V6(9,V2)(9,V5)V1~V6V7V8{a57,a68}min{l5+W57,l6+W68}=min{8+6,9+4}=13=l6+W68V8(13,V6)V1~V6,V8V7{a57}l5+W57=8+6=14V7(14,V5)V1~V8φφEND26由表三知V1V8最短路P1：V8V6V2V1最短路P2：V8V6V5V3V2V1最短路长|P1|=2+7+4=13|P2|=2+3+3+1+4=134471233227（三）通信线路布设问题（教材P209）例3.甲、乙两地之间的公路网络如图三，电信公司准备在甲、乙两地沿公路沿线架设一光缆线，问应如何架设此线路方案，以使光缆线路架设总长度最短？图三28dijV1V2V3V4V5V6V7V101510∞∞∞∞V215036∞∞17V31030∞4∞∞V4∞6∞04∞5V5∞∞4402∞V6∞∞∞∞206V7∞17∞5∞60解：本例之一步可达距离阵如G={V,E,W},V={V1V2V3V4V5V6V7}，本例G为无向图，求解过程见表四W=29Vj(lj,Vk)IJA={aij|Vi∈I,Vj∈J}hkhijIiiWlJWl}V|min{jV1(0,s)V1V2V4~V7{a12,a13}min{l1+W12,l1+W13,}=min{0+15,0+10}=10=l1+W13V3(10,V1)V1,V3V4~V7{a12,,a32,a35}min{l1+W13,l3+W32,l3+W35}=min{0+15,10+3,10+4}=13=l3+W32V2(13,V3)V1V2V3V5V4V6V7{a24,a27,a35}min{l2+W24,l2+W27,l3+W35}=min{13+6,13+17,10+4}=14=l3+W35V5(14,V3)V1V2V3V5V6V4V7{a24,a27,a54,a56}min{l2+W24,l2+W27,l5+W54,l5+W56}=min{13+6,13+17,14+4,14+2}=16=l5+W56V6(16,V5)V1~V6V7{a24,a54,a27,a67}min{l2+W24,l5+W54,l2+W27,l6+W67}=min{13+6,14+4,13+17,16+6}=18=l5+W54V4(18,V5)V1~V6V7V8{a27,a47,a67}min{l2+W27,l4+W47,l6+W67}=min{13+17,18+5,16+6}=22=l6+W67V7(22,V6)V1~V7,φEND表四（例3求解过程）30①由表四可得最短路P：V7V6V5V3V1最短距离|P|=10+4+2+6=22②还可得到自V1（甲）到任一中间点之最短路，例如V1V4最短路由表四可知为P14V4V5V3V1|P14|=186241031（四）设备更新问题（教材P212）例4.某公司设备管理部门欲制定一个五年期某设备的更新计划，要求给出这五年中购置该设备的年份及购置新设备的使用年限。在此五年中购置该设备的年初价格见表五，设备使用不同年限的维护费见表六。32年份12345年初价格1111121213表五（单位：万元）使用年数0～11～22～33～44～5年维护费用5681118表六（单位：万元/年）33解：设Vi—i年初购进一台新设备aij—