浅析有向图的环查找算法在贷款循环担保审计中的应用
陈宇(审计署成都办)
【发布时间:2013年01月18日】
字号:【大】 【中】 【小】
摘  要:随着计算机审计的不断深入和发展,传统的基于结构化查询语言(Structured Query Language,以下简称SQL)的数据审计方法的局限性开始凸显,审计实践要求我们跳出传统方法的窠臼,结合各种计算机技术,站在更高的层面,对数据进行更深入的分析。本文针对商业银行审计中常见的多家贷款企业之间循环担保的问题,提出了利用有向图对贷款担保关系进行建模,并利用环查找的算法实现了任意多家企业循环担保问题的分析和查找,克服了以往基于SQL的数据分析方法难以扩展的弱点,取得了很好的效果。

关键词:循环担保  有向图  环查找算法

一、引言

循环担保是商业银行贷款中一类比较常见的问题,循环担保的最终结果是担保落空,形成事实上的信用放款,企业一旦无力偿还贷款,贷款风险全部由银行承担,因此是商业银行信贷义务审计中必须要审查的一个风险点。
针对此类问题,已有的计算机审计专家经验采取的是一种传统的基于SQL的数据审计方法,但该方法存在一些明显缺陷,例如缺乏好的数学模型,缺乏扩展性,复用性差等。本文跳出SQL语言的窠臼,首先对循环担保的问题进行分析,后使用图论中的有向图模型对担保关系进行建模,再使用有向图的环查找算法实现了可扩展、易于复用、且能查找任意多家企业循环担保问题的方法,取得了很好的效果。

二、问题描述

循环担保有两家企业之间相互担保(即A为B担保,B又为A担保)、三家企业之间循环担保(A为B担保,B为C担保,C为A担保)以及三家以上企业互相循环担保的情况。循环担保的最终结果是担保落空,形成事实上的信用放款,企业一旦无力偿还贷款,贷款风险全部由银行承担,因此是商业银行信贷义务审计中必须要审查的一个风险点。
审计署计算机审计专家经验库中有一个基于SQL的查询方法,但该方法存在一个明显缺陷:从两家企业互相担保变为三家企业循环担保需要大量修改代码,从三家企业循环担保推广到四家循环担保需要更大量的修改代码,循环担保企业数越多,该方法的代码就越复杂,其完备性就越难保证,出错的可能也会加大。

三、有向图建模

在数学上,一个图(Graph)是表示物件与物件之间的关系的方法,是图论的基本研究对象。一个图看起来是由一些小圆点(称为顶点或结点)和连结这些圆点的直线或曲线(称为边)组成的。如果给图的每条边规定一个方向,那么得到的图称为有向图,其边也称为有向边;反之则称为无向图和无向边,如图1所示:


 
图1 有向图与无向图
针对贷款的担保关系,我们可以将其抽象为有向图,方法是:将贷款企业和担保方都抽象为有向图的结点,而担保关系抽象为从担保方到被担保方的一条有向边。例如A公司为B公司担保,则将A和B看作有向图的两个结点,A为B担保则表示为从A指向B的有向边,如图2所示:


 
图2 用有向图表示担保关系
这样,所有的担保关系最终就构成了一个有向图,例如有A为B担保,A为D担保,B为C担保,C为A担保,D为A担保这样的数据,则可以得到如图3所示的有向图


 
图3 担保关系形成的有向图
这样,查找多重循环担保的问题就转化为了在有向图中查找环(又称回路或强连通子图,即从一个结点开始经若干边后回到该结点的路线)的问题,在上图中存在两个环,即A->B->C->A和A->D->A,代表了ABC之间的循环担保和AD之间的相互担保。

四、有向图中的环查找算法

有了可靠的数学模型,接下来的问题就是如何在有向图中寻找环了,在此我们使用深度优先搜索(Depths-First Search, DFS)算法来实现环的查找,有向图用邻接表来表示,其数据结构的C语言伪代码定义如下:
/*    有向图的边结点结构  */
typedef struct node{
int adjvex;                   
struct node *next;
}EdgeNode;
/*    有向图的顶点结构   */
typedef struct vnode{
char name[MaxNameLength];   //用这个字段来存放企业名称
EdgeNode *firstedge;
}VertexNode;
/*    邻接表结构         */
typedef VertexNode AdjList[MaxVertexNum];  
/*    图结构             */
typedef struct{
AdjList adjlist;
int n,e;                      //n和e分别表示结点数和边数
}Graph;
根据上述的数据结构,图3的担保关系可以表示成如图4所示的邻接表:



 
图4 担保关系形成的邻接表
根据上述的数据结构,可以将基于DFS的有向图中的环查找算法描述如下:
算法:基于深度优先搜索的有向图中环查找算法
数据描述:G——Graph类型,用邻接表表示
        visited[n]——布尔类型数组,表示一个结点是否被访问过
        p[]——数组,保存当前路径包含的结点
输入:邻接表表示的有向图G
输出:G中的所有简单环(即不包含重复路线的环)
过程:
FindCircuit(G)
1 begin
2 根据给定的担保关系生成图G,将数组visited[n]置为FALSE
3 for G 中的每一个结点 {
4     k:=1
5     p[1]:= v
6     DFS(v)
7 }
8 end
DFS(v)
1 begin
2 visited[v]:=TRUE
3 for each u in G->AdjList[v]  {
4   if u=p[1]  {  //存在回路
5     输出p[1]…p[k],这是一个回路
6   }
7   else  {
8     If visited[u]=FALSE {
9       k:=k+1
10       p[k]:=u
11       DFS(u)
12     }
13     else {
14       p[k]:=NULL
15       k:=k-1
16     }
17   }
18  end

五、算法完备性证明

要说明上述算法能够找到一个有向图中所有的简单环,即任意的简单环v1,v2……vn都会在数组p中出现,我们采用数学归纳法进行证明,步骤如下:
1. 当n=1的时候,调用DFS过程时会使得p[1]= v1,结论显然成立。
2. 假设当n=m-1的时候,所有的简单环都在数组p中,即任意的简单环v1,v2……vm-1都存在于p中,则当n=m的时候,如果存在简单环v1,v2……,vm-1, vm,则vm必然可以从vm-1到达,即vm ∈AdjList[vm-1],因此在调用DFS(vm-1)的时候就会在第3行代码处遍历到vm结点,并在第10行代码处将其加入数组p。所以当n=m时成立。
3. 有1、2可得,上面的算法可以找出一个有向图中所有的简单环。

六、结论

在计算机技术和计算机审计技术飞速发展的今天,审计人员正积极探索传统的基于SQL的数据审计之外的新领域,将审计问题进行数学建模,利用数学算法进行分析查找有利于更加有效、更加可靠地解决问题。本文就将有向图的深度优先搜索算法应用于金融审计实践,取得了很好的效果。这有利于我们今后进一步拓宽思路,找到针对不同审计问题的审计模型和审计方法。(陈宇)




参考文献:
[1] 严蔚敏, 吴伟民. “数据结构:C语言版”. 清华大学出版社, 1997
[2] 吴子华, 张一立, 唐常杰. “离散数学教程”. 四川大学出版社, 1999
[3] 董永强. “贷款循环担保审计”. 审计署计算机审计专家经验库, 2003
【关闭】    【打印】