（基础数学专业论文）三角债问题的图论模型.pdf

摘要 三角债是指多个企业之间相互拖欠债务所形成的错综复杂的债务关 系，它是我国当前经济领域中存在的一个突出问题，严重影响企业的生 产经营和国民经济的发展。已引起经济管理部门、企业界和学术界的高 度重视。国家曾多次注入资金组织大规模清理，但收效甚微。 三角债是一种形象的说法，并不是指企业债务关系真正呈三角形， 它是指企业间的债务关系呈封闭图形。本文从三角债的实际情况出发， 用图论和网络的理论和方法研究三角债问题，建立了清理三角债的图论 模型，并根据不同情况，运用不同的方法对模型进行了定量分析。从图论 的角度来看，清理三角债就是变封闭图形为敞开图形，使企业问的债务 关系清晰明朗化，即在保持所有企业绝对债务量不变的情况下力求使债 务网络简化，使网络中所有有向弧段的权值之和为最小。本文首先利用 网络流的概念，将清理三角债的数学模型问题化成求解相应网络上最小 费用流的问题。其次提出一类网络最优化模型最小网络问题，讨论 了最小网络的相关性质及最小网络的若干充分必要条件，证明了任一网 络可通过两种基本运算化为最小网络。由此得出将任一网络化为最小网 络的方法，给出了求给定网络的最小网络的一个多项式时间算法。通过 矩阵变换，在保持系统的基本特征，即各个企业的净债务量不变的前提 下，使债务企业和债权企业完全分离，即债务企业仅负有债务而不具有 债权；债权企业仅具有债权而没有债务。同时给出了清理三角债网络模 型的图上作业法，以解决清理三角债所需投入的最少资金以及清理顺序。 使这笔资金能够合理分配，清理的债务量达到最大。 根据三角债的图论模型分析，从理论上讲，三角债的清理问题可以 在网络内得到解决。三角债关系本身并不复杂，在债务网络内可以在保 持所有点绝对债务量不变的情况下力求使债务网络简化，也就是求一系 列冲销运算，使得经过这些运算后得到的剩余债务网络的债务总和达到 最小。通过对模型求解我们得到了一种注入资金方案，即在网络图上清理 三角债问题中的资金分配方法，用以实现用有限的资金清理最大数额债 l 务目的，使得所涉及的群体中的每个成员之间都不欠债( 这里的债务是指 n 过a 业正n n n n n # ) ，即相互间无不正常的债务与债权关系。 关键词：三角债；图论模型；债务网络 中图分类号：0 1 5 7 5 a b s t r a c t t r i a n g u l a r - d e b tp r o b l e m i st h em a j o rp r o b l e mi nt h ee c o n o m i cf r o n ta t t h ep r e s e n tt i m ei nc h i n a i th a sa f f e c t e dt h ep r o d u c t i o na n db u s i n e s so ft h e e n t e r p r i s e sa n dt h eg r o w t hi n t h en a t i o n a le c o n o m ya n db e e ng i v e nh i g h r e g a r d e db ye c o n o m i cm a n a g e m e n t ，b u s i n e s s a n da c a d e m y i th a db e e n c l e a r e db yw h o l e s a l e ，b u ta l lt h e s ee f f o r t sw e r ep r o v e do f l i t t l ea v a i l t r i a n g u l a r - - d e b ti sa n o t h e rw a y ，t h a ti st os a y ，t h ed e b t so fb u s i n e s sa r e n o tt r i a n g u l a ri ns t r u c t u r e ，b u t ac l o s e d f i g u r e b o u n d e db yt h e s e e n t e r p r i s e s t h i sp a p e rp r o c e e df r o ma c t u a l c o n d i t i o n so ft r i a n g u l a r d e b t ，s t u d i e du p o nt h ev i e w so fg r a p h i ct h e o r ya n dn e t w o r k i n ga n db u i l tu p m o d e lv i ag r a p h i ct h e o r y ，a n dg i v e nq u a n t i t a t i v ea n a l y s i so ft r i a n g u l a r - d e b t i nv a r i o u sw a ya c c o r d i n gt od i f f e r e n tc i r c u m s t a n c e s f r o mt h ev i e wo ft h e g r a p h i ct h e o r y ，c l e a r i n gt h et r i a n g u l a r - - d e b ti st r a n s f o r m i n gac l o s e df i g u r e i n t oa no p e n e df i g u r e a n dt e n d st om a k et h e i rd e b t sc l e a r n a m e l y ，t r yt o s i m p l i f yt h ed e b tn e t w o r km a i n t a i n i n gt h ed e b t so fa l le n t e r p r i s e sc o n s t a n t t h i sp a p e ri n j e c t e dn e wi d e a s n e t w o r kf l o w ，a n ds h o w e dt h a tt h em o d e l s c a nb et r a n s f o r m e di n t om i n i m u mc o s tf l o wp r o b l e m s ，h e n c ec a nb es o l v e d b ys t r o n gp o l y n o m i a la l g o r i t h m s t h i sp a p e ra n a l y z e s t h ep r o p e r t i e so fa m i n i m u mn e t w o r k ，a n dn e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n sf o ram i n i m u m n e t w o r k t h ea n a l y s i spr o v e st h a ta n yn e t w o r kc a nb er e d u c e dt oo n eo fi t s m i n i m u mn e t w o r k sb yt w ob a s i co p e r a t i o n s o nt h ep r e m i s et h a ta l lt h ed e b t s o fn e t w o r ka r en o tc h a n g e d ，t h ec r e d i t o ra n dd e b t o ra r es e p a r a t e db y t r a n s l a t i n gd e b tm a t r i x m o r e o v e r ，am e t h o di sd e v e l o p e dt o r e d u c ea n y n e t w o r kt oi t sm i n i m u mn e t w o r ku s i n gat i m e b a s e dp o l y n o m i a la l g o r i t h m ag r a p h i co p e r a t i o nm e t h o di sd e v i s e dw h i c hh e l p st os e t t l et h em i n i m u m i n p u to f c a p i t a lf o rc l e a r i n gt h ed e b t sa n d t h eo r d e ro f t h e i rc l e a r i n g f r o mt h ea n a l y s i so ft h eg r a p hm o d e lo ft r i a n g u l a r - - d e b t ，c a n c e l l a t i o n s o f t r i a n g u l a r - - d e b tc a nb es o l v e dw i t h i nt h ed e b tn e t w o r k i nf a c t ，t r i a n g u l a r - - d e b tr e l a t i o n sa r en o tc o m p l e x ，w ec a nt r yt os i m p l i f yt h ed e b tn e t w o r k 1 1 1 m a i n t a i n i n ga 1 1d e b t so fa l le n t e r p r i s e sc o n s t a n t ，t h a ti st os a y ，t r yt 0s e e ka s e r i e so fw a s hc a l c u l a t i o n si no r d e rt om a k et h et o t a lo fd e b t st oi r r e d u c i b l e m i n i m u m w ec a nd e s i g nap r o j e c to fi n j e c t i o no ff u n d st om a k ea l lm e m b e r s o f d e b tn e t w o r ko u to fd e b t k e y w o r d s ：t r i a n g u l a r - - d e b t s ；g r a p hm o d e l ；d e b tn e t w o r k c l cn u m b e r s ：0 1 5 7 5 i v 第一章绪论 第一章绪论 1 1 选题的目的和意义 三角债是指人们对企业之间超过托收承付期或约定付款期应当付而未付的拖欠 货款的俗称。也就是企业间相互拖欠货款，构成复杂错综的债务链，以致于成品资金 无法转变为货币资金，严重阻碍流动资金周转的现象。9 0 年代初，三角债成为中国、 俄罗斯、东欧诸国经济发展的一大障碍。其实，早在8 0 年代中后期，我国的三角债问 题已经形成。到了9 0 年代，三角债已成为我国企业，尤其是国有企业的顽疾之一。我 国企业债务拖欠数额是十分巨大的，通过银行办理“拖收承付”表现出来的拖欠金 额只是一小部分，大量的拖欠发生在“拖收承付”以外。三角债不仅涉及到个人和 农民，也涉及到商业和外资企业；不仅涉及到全民所有制，也涉及到工业企业；不 仅企业问的拖欠，企业与财政，企业与银行，银行与财政之间也有拖欠。债务主体 之间的关系广泛而复杂，跨地区、跨行业、跨部门的债务纠纷相互交织在一起，而 且许多债款的拖欠时间很长，短则一两年，长则七八年。9 0 年代末，国家曾有组织、 有计划、有步骤地清理三角债，取得了一定的成效。但相互间拖欠的问题并没有得 到根本治理，呈现出拖欠金额逐年上升、拖欠时间越来越长、拖欠范围不断扩展、 拖欠死帐逐年增长等特点。三角债已成为我国企业，尤其是国有企业的顽疾之一“1 。 三角债的危害甚多，其主要表现如下： 1 造成了虚盈实亏 三角债使商品销售后货款未能按期回笼，造成供需之间的商品交换活动没有形 成一个完整的周期。把三角债计入销售收入，并结转利润、计提上缴税金、进行利 润分配，则造成次序颠倒，即分配在前、交换应获成果在后。企业将可能因此而虚 盈实亏、丧失后劲，甚至造成资不抵债、破产倒闭。这种副效应在一段时间里，有 可能被假象所掩盖，但迟早要暴露出来。 2 制约了企业发展 被三角债困扰的企业，其资金长期被债务人无偿占用。为了维持生计，企业被 迫增加银行贷款，从而扩大了非正常的利息支出。由于相互拖欠，使得大部分国有企 业出现“资不抵债”的现象。一部分效益差或产品严重积压的企业把其亏损暂时转 三角债的图论模型分析 嫁给另一部分效益较好的、产品积压较少的企业，被占用资金的企业不得不去增加银 行贷款，来缓解运营中的资金不足。由于积累的巨额的未清偿的债务拖欠使企业不能 进一步向银行申请贷款，或难以申请到信贷，结果使一些效益好的企业最终也因缺乏 流动资金而难以扩展生产。为了清理三角债，各单位组织了庞大的清欠队伍，并借 助公安、司法机关的力量进行清欠。企业用于清欠的差旅费、诉讼费、奖金、应酬 费等支出非正常地扩大了销售成本，增加和创造机会损失制约了企业的发展。 3 败坏了社会风气 三角债的危害已经远远超出了经济范畴，成为腐蚀人们思想、败坏社会风气的 公害。欠钱还钱是自古以来的道理。但一些债务人抱着“要钱没有，要命一条”的 态度，企图赖账不还；一些债务人利用债权人急于汇款的心理，以明的或暗的方式 向债权人要好处、吃回扣，使正常的欠债还钱附加了非正常的条件；一些不法分子 利用企业管理的疏漏，以三角债为名，内外勾结，搞资金体外循环，做个人买卖， 挖企业的墙角。 目前三角债已成为困扰国有企业生存发展与提高经济效益的重要因素之一。如 何解决国有企业的三角债问题，是搞活企业，转换企业经营机制的前提条件之一。 1 2 三角债的研究现状 1 2 1 三角债的成因 具体剖析每一笔三角债，其原因是多方面的，每笔三角债形成的原因也不尽相 同。总的说来，其共性原因主要有以下几个方面： 1 ) 阻碍经济发展的深层次矛盾没有得到彻底解决。从经济发展史的角度来看， 资本主义社会形成的初期，市场经济处于幼稚阶段，债务链现象也曾较为严重。随 着市场经济的发展，这一问题才得以逐步解决。目前，我国从计划经济向市场经济 转化的时间还比较短”3 ，许多深层次的矛盾还没有得到彻底解决。 2 ) 基本建设规模超大，与财力不相适应。一些单位在新增固定资产和技改项目 中，违背量力而行、量入为出的原则，资金不足，仓卒上马，往往造成拖欠工程款 和材料款维持上不去、停不起的半截工程。工期势必一拖再拖，而工期拖得越长， 资金投入就越大，三角债就越严重。 3 ) 背离国情，违背经济规律。一些企业因盲目决策失误、盲目追求产值或盲目 第一章绪论 收购，造成资金沉淀。为了松动库存，实行赊销，致使企业间互相拖欠。 4 ) 许多企业同时担当债务人和债权人的角色，在清欠问题上，从本企业的利益 出发，对偿还欠款的态度不积极，使清欠工作迟迟不能落实。 5 ) 相当一部分企业不景气，缺乏偿还债务的能力。 6 ) 国家对清理三角债的问题缺乏行之有效的措施。 1 2 2 当前三角债的研究现状 三角债已引起经济管理部门、企业界和学术界的高度重视。国家曾多次注入资 金组织大规模清理。时至今日，三角债清理虽已收到一定的效果，但距离我们的既定 目标还有很大差距。到目前为止，国际经济学界在如何清理三角债的问题上，主要有 以下三种设计方案： a 将债权转化为股权。 b 改革资金市场，建立正常的惩罚制度以确保商业信用的发展。 c 成立一个“清债中心”注入必要的清债资金。 对于这些方案，经济学界也提出了一系列的看法”1 ： 其一，如果将债权转化为股权，可以使部分债务链迅速消失，但如果全社会都这 么做，又会导致新的问题是，对于债权企业来说，他当初出借债务，并不是为了投资， 将债权全部转化为股权，债权企业仍然得不到急需的流动资金用于正常的生产，即这 一方案并不能缓解流动资金被占用的问题。 其二，改革资金市场与建立惩罚制度的方案还有待于企业制度的真正改革。 其三，成立“清债中心”，在中国与俄罗斯均已实行，但经验事实证明，成立“清 债中心”并不能彻底解决三角债问题”1 。 1 3 研究内容及思路 对于三角债问题，现已有大量研究，但大多数侧重于定性方面，讨论其原因和 对策，而对具体三角债该如何清理，资金如何使用才能得到最有效的清理效果这样 的定量分析比较少。三角债是一种形象的说法，并不是指企业债务关系真正呈三角 形，它是指企业间的债务关系呈封闭图形。本文从三角债的实际情况出发，用图论 和网络的理论和方法研究三角债问题，建立了清理三角债的图论模型，并根据不同 情况，运用不同的方法对模型进行了定量分析。从图论的角度来看，清理三角债就是 三角债的图论模型分析 变封闭图形为敞开图形，使企业间的债务关系清晰明朗化，即在保持所有企业绝对 债务量不变的情况下力求使债务网络简化，使网络中所有有向弧段的权值之和为最 小。本文利用网络流的概念，将清理三角债的数学模型问题化成求解相应网络上最小 费用流的问题。并提出一类网络最优化模型最小网络问题，讨论了最小网络的 相关性质，获得了最小网络的若干充分必要条件。证明了任一网络可通过两种基本 运算化为最小网络，由此得出将任一网络化为最小网络的方法，给出了求给定网络 的最小网络的一个多项式时问算法。通过矩阵变换，在保持系统的根本特征，即各 个企业的净债务量不变的前提下，可使债务企业和债权企业完全分离。即债务企业 仅负有债务而不具有债权；债权企业仅具有债权而没有债务。而且给出了清理三角 债网络模型的图上作业法，以解决清理三角债所需投入的最少资金以及清理顺序。使 这笔资金能够合理分配，清理的债务量达到最大。 第二章凰论基础知识 第二章图论基础知识 图论是研究离散对象二兀关系系统的一个数学分支，是一门应用十分广泛的学 科，它已广泛地应用在物理学、化学、通讯、管理、电子计算机等各个领域。在实 际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决。 随着科学技术的发展以及电子计算机的出现与广泛应用，图论的理论得到进一 步发展。将庞大复杂的工程系统和管理问题用图描述，可以解决很多工程设计和管 理决策的问题。图论受到数学、工程技术及经营管理等各个方面越来越广泛的重视。 为了叙述方便，本章仅简单介绍后面将要用到的图论的一些基本概念。 2 1 图 图g 是指一个有序三元组杪( g ) ，e ( g l y ( g ”，其中v ( g ) 是非空的顶点集，e ( g ) 是不与矿( g ) 相交的边集，而( g ) 是关联函数，它使g 的每条边对于与g 的无序顶点 对( 不必相异) 。若p 是一条边，而“和v 是使得g ) = u v 的顶点，则称e 连接“和 v ；顶点“和v 称为e 的端点。某个边的两个端点相同，称该边为环”1 。 2 2 链和囤 若图g 的一个点和边的交替序列扣儿，e i l , v i 2 ) e i 2 ， e i k - v 。 满足 = 饥，v 。) 0 = 1 , 2 ，k 一1 ) ，则称这个点边序列为一条从v 。到v 。的链，简称 v 。v 。v 。) 。 在链和n ，v 。v 。 中，若v 。= v 。，则称之为圈“1 。 2 3 赋权图 对图g 的每条边p ，赋以一个实数( 甸，称为边e 的权。每个边都赋有权的图称为 赋权图。若日是赋权图的个子图，则日的权，旧) 是指它的各边的权和w 0 ) 。 p e f h l 2 4 有向图和弧 由点集y 和弧集a 组成的图d = ，a ) ，其中v 是点集，a 是弧集。所谓弧就是 三角债的图论模型分析 点与点之间有方向的线，即点集矿的有序偶( v ，) ，v i 是弧的起点，而是弧的终点， 一般用v 记点，用d 记弧。 2 5 网络和流 网络n ：给一个有向图d = ( v ，4 ) ，在矿中指定了一点，称为发点和另一点，称 为收点，其余的点叫i a j 点( 记为，) 。对于每一个弧“，”) 4 ，对应有一个c o f ，) 0 ( 或简写为c j ) ，称为弧的容量。这样的g 叫作一个网络。记作n = ( 矿，爿，c ) 。 若s v ，则用j 表示y s ，若厂是定义在g 的弧集爿上的实值函数，并且 k 爿，则用厂k ) 表示( 口) 。若k 是形为p ，罗) 的弧集，则把p ，j ) 记为+ p ) ， 口k 而把厂晦，s ) 记为f 一$ ) 。 网络中的流是指定义在a 上的一个整数值函数厂，使得 0 厂0 ) c 0 ) ，对所有d 一成立 厂一( v ) = f + ( v ) ， 对所有v e ，成立 对于任意点v v ，记 4 + 0 ) = ( v ，v ，) e 爿1 4 一( v ) = ( v ，v ，) e 一 “1 第三章三角债的图论模型 第三章三角债的图论模型 三角债现象的背后隐藏着许多错综复杂的经济矛盾。企业拖欠除一些企业因存 有“欠款有益、欠款有理”的想法而故意拖欠以外，主要是因为资金存在缺口，企 业不得不拖欠。企业相互拖欠有两种基本形式：一种是环型拖欠，债务链呈环状结 构，每一个环节既是债务人，又是债权人，每个当事人的债权与债务均可以抵消。 另一种是线性拖欠，债务链呈线形结构，最初债权人为净债权人，中间当事人的债 权债务可以相互抵消。任何拖欠都是这两种拖欠形式的复合。 3 1 模型 下面建立三角债的图论模型。 目的：为了最大限度地减少企业间的三角债 条件：用来清理“三角债”的资金只通过企业的丌户银行在帐面上进行划拨，以 确保资金不得挪为他用。 设有”家企业，记为v = h v z ，“ ，其中某些企业存在一定数量的债务关系， 若企业v ，对v ，有一笔欠款，则画一条从v ，到v ，的有向弧，弧的权即是v ，欠v ，的债额。 将弧的全体记为a ，这样就得到一个描述债务关系的赋权有向图d = ( v ，a ) ，简称债 务图。显然在债务图中，可能会出现企业v 。欠v ，若干笔债，即v ，到v ，有若干条有向弧， 同样也可能存在v ，欠v ，若干笔债务( 即v ，到v 有若干条弧) ，从实际意义上讲，二个相 反的负债额可进行相互的抵消。因此，为研究方便起见，有必要对债务图作一些必要 的简化( 例如图3 1 ) 。 v -v 8 v 2 卜v 3 图3 1 简化后 三角债的蹦论模型分析 设q ，d ：，n 。是v ，到v ，的平行有向弧，并以日，表示负债额( f 2 1 ，2 ，k ) ，即点v ， 处各出弧上的权之和，记为曲= w 同时v ，到v ，的平行有向弧有乜，6 ：，6 ，条，也 p 以b ，( i = 1 ，2 ，t ) 表示负债金额，即点v ，处各入弧上的权之和，记为b ( 1 ) 若d ，一b 。，即企业v ，欠企业v ，的总债额等于企业v ，欠企业v r 的总债额，则删 除v f 及v ，到v ，到v ，的所有有向弧。 ( 2 ) 若日， 6 ，即企业v ，欠企业v ，的债额大于v ，x v 的债额，则删除到v ，及v ，到 ”的所有有向弧，作一条从v f 到v ，的有向弧，权为a ，一包 ( 3 ) 若n 。 o ) ，t = v 矿k ( v ) 2 ，h 2 。此外，从v ，到v ，无弧，则约定盯o 。这 样，弧集一可以通过赋权集来确定，因而网络= 缈，a ，) 可简记为n ：缈，w 1 。弧 ( v ， ) 上的权w r 有时也记为w ( v ，h ) 。 现在的问题是对给定的网络= ( 矿，) ，在保持h ，不变的前提下，修改各弧一匕的 权w p 的值，使扣眇) 达到最小，这样所得的网络扣( ) 为最小网络，对于给定网络求其 最小网络的问题称为最小网络问题“，。 4 2 1 基本定理 在网络= ( 矿，) 中，如果结点”处既有权不为。的入孤，又有权不为。的出弧，则 称v ，为过渡点。1 。 下面定理1 的结论显然成立。 定理1 在网络n = ( 矿，w ) 中，结点”不是过渡点的充分必要条件是。，6 ，1 0 。 定理2 对网络n = ( 矿，矿) ，在死o = 1 ，2 ，行) 保持不变的条件下，不论如何取值， 总有一( ) 寺i h i j 吉【( ”一( 胪。) 】：寻( z b ；+ 巧) ： 三，( a i + b i ) 三冲f | = 三军例 证毕。 定理3r i j - t n = ( y ，) ，在保持而( f = 1 ，2 ，刀) 不变的条件下，对其权进行修改后 所得的网络记为n ( 矿，矽) ，则n ( 矿，w ) 是g o ，w ) 的最小网络的充分必要条件是 n ( 矿，w7 ) 中无过渡点。 为证定理3 ，先定义网络n = o ，w ) 上的两种运算并引入两个引理。网络 第四章模型分析 = o ，矽) 的一条有向途径是n = ( 矿，w ) 中某些结点的一4 序yj j v i o ) i l v i2 v i i ，其 中，( w + ) e 爿，p = 0 , 1 ，k 一1 ) ，a 是n = 缈，w ) 的弧集。在此序列中结点可重复出 现，但弧不能重复。如果“= v 。，则称其为= ( y ，w ) 的一条有向闭途径。由于假定 网络= 缈，w ) 中没有环弧( * ，”) ，且不同时有孤( v 。 ) 和如，* ) ，因此任何条有向闭 途径的长度必定大于2 。 运算1 对n = o ，w ) 中一个有向闭途径c ，设c 上所有弧的权的最小值为，。 将c 上各弧的权减去w 。所得值作为各弧的新权值，去掉零权弧。 运算2 对n = ( y ，w ) 中一条非闭的有向途径p = w t v ：纭2 ) ，设p 上各个弧 的权的最小值为心。将p 上各弧的权减去，所得之值作为各弧的新权值。如果v 。与 u 间无弧，则添加一条新弧o n w ) ，并赋权值w i ，：如果有弧v o ，) ，则该弧的权值加上 w l ，。：如果有弧( v 。，v 。) ，则该弧的权值减去w 1 ，且当差为负数时，将该弧反向，用差的绝 对值赋权。去掉零权弧。 容易证明下列两个引理成立。 引理1 对网络n = ( 矿，矿) 施行运算l 和运算2 后，各结点的忍( f _ 1 , 2 ，以) 值不变。 引理2 对网络n = ( 矿，渺) 施行一次运算l ，网络的总权值减小k w 。 这里七是施行运算1 的有向闭途径上弧的数目，圪是这些弧上权的最小值，对网 络n = ( 矿，矿) 施行一次运算2 ，网络的总权值至少减小( k l 加o ，其中k 是施行运算2 的 非闭的有向途径上弧的数目，w 。是这些弧上权的最小值。 现在来证明定理3 。 必要性：如果n 缈，w ) 中有过渡点，则o ，w ) 中要么有长大于l 的非闭的有向 途径，要么有长大于2 的有向闭途径。由引理i 和引理2 ，可对( 矿，w ) 继续施行运算l 或运算2 ，可使网络的总权值减少。这与n7 0 ，w ) 是n ( v ，w ) 的最小网络矛盾。 充分性：设( 矿，w7 ) 中无过渡点，则由定理1 ，对每个i = 1 , 2 ，n ，要么口，= 0 ， 要么b ，= 0 。 从而玑= 口j 或m = 一眠( 浮1 , 2 ，n ) 。因此， 一( ) 2 去( w7 一+ ( w ，) ： 三角债的图论模型分析 刘1( w 。+ ( w 。】：i 1 ( 6 ，+ ) - - 1 , 。，) ： 三2 莩( 一+ 肼) 丢莩i 一一乩| = i 1 莩例 由，2 对任何赋权集矽，一( 矿) 的最小值去i h i i ，而n 妒，w ) 的权值达 到了i 1l h i l ，故杪，w ) 是( y ，矿) 的最小网络。证毕。 定理4n ( ，w ) 是u ( v ，w ) 的最小网络的充分必要条件是n ( y ，w ) 中无长大于 1 的有向途径。 证明：由于杪，w ) 中无长大于1 的有向途径当且仅当n ( 矿，w ) 中无过渡点， 由定理3 e l i 知结论成立。证毕。 定理5 任一网络n = ( 矿，w ) 总可经过有限步运算1 和运算2 化为最小网络。 证明：对n = ( v ，w ) 中每个有向闭途径c ，对其施行运算1 后，必至少有一条弧的 权为0 ，这样有向闭途径c 被破为较短的有向途径，因此，总可经有限步后破掉所有长 大于i 的有向闭途径。 对于n = 杪，w ) 中任一结点v ，设尸是从v 出发的一条长大于1 的非闭有向途径。 对其施行运算2 后，至少有其上一条弧的权变为0 。这样，被断为更短的有向途径，且 这一过程不会产生新的从v 出发的长大于1 的有向途径。如此经过有限步后，便可将 从v 出发的长大于1 的有向途径全部破除。取遍n = ( 矿，w ) 的所有点进行上述过程，即 可看出经有限步后，网络中不再含有长大于l 的有向途径。因此，根据定理4 ，经有限步 后网络便被化为最小网络“。证毕。 4 2 2 算法 设v i 1 2 i ：v 。是n = ( 矿，w ) 的一条有向途径，且终点处已没有出弧不在该途径 上，则称这条有向途径为从v 。出发的一条极长途径。由上节的讨论知，欲求一个给定 网络的最小网络，只要按运算1 和运算2 破除网络中所有长大于1 的有向途径( 包括闭 途径) 即可。具体地，就是逐次找网络中长大于1 的有向途径，按运算1 和运算2 修改其 权，并删去权为0 的弧。这提供了求最小网络的一种算法思想：任取网络中一点v ，找 一条从u 出发的极长途径，并检查其长度。当长度大于1 时，若途径是闭的，则按运算1 第四章模型分析 修改该有向闭途径上的权：否则，按运算2 修改其权。当长度不大于l 时，改找其他极长 途径。反复执行这一过程，直至网络中没有长度大于1 的有向途径为止。 找极长途径可使用简单的搜索法：从v 。出发，找k 的一个出邻点h 再找v 的一 个出邻点v ：，如此反复，直至到达某个点v 。，v 。无新的出邻点为止。这里所谓v 的 新的出邻点，是指v 。的一个出邻点，它在此前尚未作为v 。的出邻点被该途径选取过。 为实现上述算法思想，引进权值矩阵和出邻集的概念“1 。有向网络n = ( 矿，w ) 的 权值矩阵定义为矿( ) = 如，) ，其中w ”的取值为从v ，到v j 的弧( u ) 的权值。如果v ， 到无弧，则规定w ，为0 。对任何结点v v ，v 的出邻集定义为 n + ( v ) = 扣ev l w ( v ，v ) o _ 各结点的出邻集可以完全由权值矩阵决定“。 上述算法思想可通过逐步修改权值矩阵和结点的出邻集来实现。 算法输入：初始网络n o ，) ： 输出：n ( v ，w ) 的最小网络的权值矩阵。 第。步构造缈，w ) 的权值矩阵( ) ，并求出各结点的出邻集。令旷= v 。 第l 步任取 。旷，令日= o ，k = 0 。 第2 步若出邻集n + v 。) 中有某结点v 一一，使“j i ，v ) h ，则执行下步：否则转第 4 步。 第3 步令h = h u v 。，v 。+ 。k t = k + 1 ，转第2 步。 第4 步若= 0 ，令n + o 。) = v v l w ( v , 0 ，v ) 0 ) ，转第7 步，若k = 1 ，则令 n + v 。) = n + v m ) v 击= o ，h = a ，转第2 步：其余情况，执行下步。 第5 步取w o = m i n w ( e ) ，对所有弧e h ，令w 0 ) = w 0 ) 一，对于任何 e e h 0 一，v ) 日，若w 0 。，”) = o ，则+ “，) = n + ( v 。) ( v 。 第6 步若m = m ，转第l 步：否则w ( v n ) = w 如。m ) + w o ，n + 如。) = n + d 。) u b k 转第l 步。 第7 步令矿= 矿如，o ) 。若吲a ，转第1 步：否则，转停止，输出当前的权值矩阵。 4 2 3 算法分析 算法反复在网络中找极长途径，并执行运算1 和运算2 。算法用矿表示可选作极长 三角债的图论模型分析 途径起始点的结点集合。在初始阶段，旷= y 。算法在运行过程中，不断地将出邻集成 为空集的结点从旷中删除掉( 第7 步) ，因为从这些点出发已不可能再得到长大于l 的 有向途径。 算法在第l 步从矿中任取一个起始点v 。丌始找极长途径。算法第2 步和第3 步是 极长途径的反复生长过程。其中日记录极长途径上已生长出的弧的集合。当极长途 径不能再生长时，转第4 步判断途径的长度。如果长度为1 ，则临时将生长出的v 。的邻 点u 从”。的邻点集中去掉，转到第二步，找从出发的其他极长途径：如果长度为o ， 说明从这点出发已不可能得到长大于1 的有向途径，故转第7 步将其从旷删除掉，然后 转第l 步，取其他结点作为出发点继续找极长途径。但应注意，在算法第4 步转第2 步时 临时修改了v ，。的出邻集，实际上v 。还拥有第4 步被删去的那些出邻点，因此在转第7 步之前，要将v ，。的出邻集还原，以便以后作为其他途径的中途点时使用。算法在第 5 步和第6 步执行运算1 和运算2 。对所找到的极长途径，修改弧上的权值，对权变为0 的 弧，修改相应的出邻集。此外，对于非闭的极长途径，需要添加一条从起点指向终点的 弧，并修改相应的出邻集。 在第7 步，如果例= a ，则说明网络中己没有长大于l 的有向途径，由定理4 ，当前 的网络便是原网络的最小网络。所输出的权值矩阵已含有该最小网络的所有信息。 现在来考虑算法的时间复杂性。算法在每确定一个v 。后，便进行找有向极长途径并修 改其权的循环过程这个过程至多需要p ( 栉2 ) 次基本运算。由算法可见，进行一次找有 向极长途径并修改其权的过程之后，网络的总权值至少降低w o ( 1 ) 。由定理2 ，至多 需要进行w u 一去蚓次这样的修改，便可将网络化为最小网络。因此，算法的时间 胁毋妒卜。 第四章模型分析 4 3 图上作业法 在债务网络= ( y ，一，) 中，现假设银行准备投入数额为 资金专门解决这些企 业的三角债问题，希望这笔资金能够合理分配，使清理的债务达到最大。那么，就 存在两个问题： ( 1 ) 为了将债务全部清理，从外部至少要注入多少资金，即注入资金的最少数目 为多少? ( 2 ) 应当给谁注入资金，注入顺序如何? 债务清理程序是怎样的? 4 3 1 方法一： 一般地称所有企业的总债务量即全部权值之和为三角债的总规模记为m ，但有 重复计算的部分，如下所示： 111 vj v 2 卜v 3 v d 其总规模为m2 3 。如果v 。拿出资金1 还给v ：，v ：再将收到的资金还给v ，如此 下去就可以解决整体