“三角债”问题的图论模型，本文主要内容关键词为：模型论文,图论论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
“三角债”是一种经济现象，它往往困扰着当事企业，使之一筹莫展。本文提供清理三角债问题的一个数学模型，由于其结果的合理性和操作的简单性，因而具有可行性，可供有关部门在宏观调控中加以应用。
1 三角债问题的基本特征及处理原则
如称欠债企业为“债户”，被欠企业为“债主”（合称为债务关系的“当事人”），那么“三角债”问题的基本特征就是：大多数的当事人既是债户，又是债主，既欠别人的，也被别人拖欠，形成复杂的债务关系。
一个实例：当事人A[,1]…，A[,s]间的债务关系，如表1所示：
m）；反之，设r[,i]＝0（i＝1，…，m）。则由引理4知a[,i]＝0或b[,i]＝0，这时h[,i]＝a[,i]或－b[,i]，但h[,i]是定值，因而对任何i＝1，…，m，a[,i]和b[,i]都不能再变，由引理2知，Z（G ）已达到自己的最小值。
现在的问题就归结为：按运算Ⅰ、Ⅱ或Ⅲ， 在有限步内能否使图G在h[,i]不变的情形下，使r[,i]＝0（i＝1，…，m）？我们证明了如下
定理2 对双赋权图G＝（A，E），通过有限次运算Ⅰ、Ⅱ或Ⅲ，必可达到
r＝…＝r[,m]＝0。
略证 若G中有圈，按Ⅰ或Ⅱ进行调整，每施行一次，破一个圈，至少一弧变为零权弧被抹去。因此，至少有两个顶点的出入积分别减少一个整数。因此，经有限次后，G变成无圈图G′。进一步可以证明对图G′施行有限次运算Ⅲ，可使其r′[,k]＝0。
这样就使问题得到了解决。但还有几个问题值得深入研究：
①无圈图G ′经有限次调整Ⅲ可化为无过渡点图的已知证明很复杂，有无简单证明？
②Z（G）达到最小与B（G）达到最小的关系是什么？
③一个m顶点图（或n弧图）使Z（G）达到最小的最少计算步骤是多少？或问算法Ⅰ、Ⅱ、Ⅲ是否为多项式的？
④此问题有无代数解法（比如，表上作业法）？