关联矩阵在图论中的应用及树搜索算法

图论起源于18世纪数学家Euler研究的Konigsberg七桥问题，他的抽象与论证的方法开创了图论科学的研究。一个图G定义为一个偶对（V，E），记为G=（V，E），分别用V（G）和E（G）表示图G的顶点集合与边集合。一个图的边与顶点、边与回路、边与割集的关联性质可以用矩阵来表示，把表示边与顶点的关联关系的矩阵称为关联矩阵。

设图G的边数和顶点数分别为q，p，令

则称由元素mij（i=1，2，…，p，j=1，2，…，q）构成的p×q矩阵为图G的完全关联矩阵，记为R。

在图G中，如果从顶点V到顶点V′有路径，则称V和V′是连通的。如果对于图中任意两个顶点Vi，Vj∈V，Vi和Vj都是连通的，则称图G为连通图。设图G=（V，E）是一个连通图，当从图G中某一顶点出发遍历图G时，将边集E（G）分成两个集合A（G）和B（G）。其中A（G）是遍历图时所经过的边的集合，B（G）是遍历图时未经过的边的集合，称子图G1是连通图G的生成树。(www.xing528.com)

树搜索法通过以一个节点为起点，陆续搜索与该节点相连的节点来分析网络拓扑结构。根据搜索方法的不同，树搜索法包括深度优先搜索法（Depth First Search，DFS）和广度优先搜索法（Breadth First Search，BFS）。

深度优先搜索法采用“先进后出（First In Last Out，FILO）”的原理；广度优先搜索法采用“先进先出（First In First Out，FIFO）”的原理。深度优先搜索法算法是一个递归的循环计算过程，该过程可以设计为一个递归函数。在进行机电暂态模型向电磁暂态模型转换的过程中，由于需要在建模界面的平面图中确定每个节点的坐标，而PSCAD/EMTDC中桌面的平面图尺寸是确定的，为了防止节点坐标超出最大的作图区域，在转换过程中，希望从某一个节点开始作为树根，依次找到与该节点有关的最长的生成树，并根据该生成树反向搜索出与树枝相连的连枝。本书提出的模型转换算法中采用了深度优先搜索算法。