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

第十章?????? 图与网络 赵 玮 主要内容： 10.1 基本概念 10.2 最短路问题 （一）Bellman最优化原理 （二）Dijustra算法（双括号法） （三）通信线路布施问题 （四）设备更新问题 10.3 最小生成树 （一）基本概念与理论 （二）Kruskal算法（加边法、破圈法） （三）丢边法（破圈法） 主要内容： 10.4 最大流问题 （一）基本概念 （二）双标号算法 10.5 最小费用最大流 （一）基本概念 （二）求解算法 § 10.1 基本概念 1 图 def1：一个无向图（简称为图）G是一个有序的二元组，记为G=(V, E)。其中 V={V1…Vn}称为G的点集合，E=(eij)称为G的边集合，evj为连接VV与Vj的边。 若N和E均为有限集合，则称为G为有限图，否则称无限图。 若G中既没有有限回路（圈），也没有两条边连接同一对点，则称G为简单图。如右图之（a），右图之（b）不是简单图。 若G为简单图，且G中每个点对之间均有一条边相连，则称G为完全图。如图（a）是简单图，但不是完全图。 def 2：一个有向图G是一个有序的二元组，记为G=(V, A)，其中V=(V1V2…Vn)称为G的点集合，A={aij}称为G的弧（有向边）集合，aij是以Vi指向Vj的一条弧。 |V|=n表示G中节点个数为n，此节点个数n也称为图G的阶 |A|=m表示有向图G中弧的个数为m 任一顶点相关联（连接）的边的数目称为该顶点的次数 例：下示图G1是图G的子图，图G2是图G的生成子图。 4 赋权图（加权图）与网路 def 5：设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为网络。 § 10.2 最短路问题 def 6：设G =（V, A, W）为一个赋权有向图，Vs为指定发点，Vt为指定收点，其余为中间点，P为G中以Vs到Vt的一条有向路，则称 为路P的长度，若有 则称 为G中从Vs到Vt的最 短路， 为该最短路的长度（此中F为G中 所有从Vs到Vt的全体有向路的集合）。 最短路问题在企业厂址上选择，厂址布 局，设备更新，网络线路安装等工程设计与 企业管理中有重要应用。 （一）Bellman最优化原理 1 命题1：若P是网络G中从Vs到Vt的一条最小路，Vl是P中除Vs与Vt外的任何一个中间点，则沿P从Vs到Vl的一条路P1亦必是Vs到Vl的最小路。 证明（反证）： 若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的一条最小路矛盾。 2 算法思想： 设G中从Vs到Vt的最小路P：Vs…Vj…Vk…Vt，则由上述命题知：P不仅是从Vs到Vt的最小路，而且从Vs到P中任意中间点的最短路也在P上，为此可采用如下求解思路： ⑴ 为求得Vs到Vt的最短路，可先求得Vs到中间点的最短路，然后由中间点再逐步过渡到终点Vt。 ⑵ 在计算过程中，需要把V中“经判断为最短路 P途径之点i”和“尚未判断是否为最短路P途径 之点j”区分开来，可设置集合I和J,前者归入 I，后者归入J，并令算法初始时，I中仅包含 Vs，其他点全在J中，然后随着求解过程的进 行，I中的点逐渐增加（相应J中的点逐渐减 少），直到终点Vt归入I（相应J=φ），此时 迭代结束。I称为已标号集合,J称为未标号集合。 ⑶ 为区分中间点Vk是否已归入I中以及逆向求解最短路的方便，可在归入I中的点Vj上方给予双标号（lj, Vk），此中lj表示从Vs到Vj最短路的距离，而Vk则为从