计算最小支撑出树的一种简便算法.pdfVIP

维普资讯 1999年 12月 应用数学与计算数学学报 第 13卷 第 2期 Dec 1999 CoM M oN APPL．M ATH AND COM PUT V0l_13 No2 @ 7～7弓 计算最小支撑 出树 的一种简便算法 翟 晓燕 (=)2z (广州大学模糊系统与知识工程研究所 ，广州 510091 0／ 摘 要：本文通过对嗍络中有 向支撑出树性质的研究，提出了在有 向网络图中 寻找以某一定点为根 的最小有向支撑 出树一种较简便的计算方法，并给 出了应用该 算法进行实际操作 的一个算倒 ． 4．-- ． ．～ ． 关键词：网络，以一点为根的支撑出树，曼：堂些： 闩伺 阐 萄 1．预备知识 同德 国 。f IJ 口 在运输网络 中，我们常常需要将一些物资从某地发送到各分站，然后再从各 分站运送到其它各地，同时要求其总运费晟少．这类 问题实际上可以转化为在网 络 中寻找以某一点为根的晟小支撑 出树的问题．虽然 J．Edmonds等提出的晟优分 支算法 1【-2】为这类 问题的解决提供 了一种可行的计算方法，然而 由于其计算过程 中往往需要对原 网络 图进行多次 “收缩”、计算和 “展开”，因此在实 际操作时 比 较复杂．本文在文章 3【—4】讨论了支撑树有关性质 的基础上，提 出了在网络 中 寻找以某点为根的晟小支撑 出树的一种较为简便的计算法、以下我们所讨论的有 向图均视为严格的，即无环且任何两条端点相 同的弧都不具有相 同的方 向． 通常我们把有 向图D= (A)( 是 D 的顶点集， A是其弧的集合，可分别 记为 V(D)和 A(D))中点 Ui与弧 毗 的有 限交替序列 l：voa nz。， ， 。 (其 中 m= ( … )或 ai= (… 、vi))称为点 o与 之 间的半通道，并称任意两 点 之间均有一条半通道相连 的有 向图为连通 图；若半通道 l中所有 均不相 同，且 啦= (，Vi+1) =0，l，… ，n—1))，则称 l为从点 0到 口 的一条路，记 为 f_l(vo，l；n) 或 f_( Vl， ， )、并称路 l中终点 的弧 a一 = (一 ， )为f的终端弧；若在 路 f中还有 = 则称 f为一条 回路 ． 定义 l 设 T= (AT)是有 向图 D = (A)中的子 图 (AT A)，0∈V，若 V∈V，在 T中存在唯一一条从 V0到 的路，则称 是 以 o为根的支撑 出树，简 称为支撑 出树． 有 向图D ：(A)和定义在 D 的弧集 A上的一个非负数 ”(n)(n∈A)称之为 网络 ，记 为 N = (D，)． 定义 2 设T = (A )是网络N= (D，”)中以VO为根的支撑 出树，若 Ⅳ中任一 棵 以 为根的支撑 出树 T都满足： ”() ” )(其 中w(T)=∑。A㈣ (。)，A(T) 表示 的弧集合)，则称 为 Ⅳ 中以Vo为根 的最小支撑 出树 ． 为 了讨论 的方便 ，我们再 引入 以下有关运算符号．设 D = (H，A)和 Dz= 本文 1999年 5月 15日收到 维普资讯 应用数学与计算数学学报 13卷 ( ．2)均为有向图，D1+D2=D D= (A)是指：V：HU ，J4=A1UA2；若还有 H ，AL A2，则 D2一Di=D，D