关于 Fleury 算法的一点注记

A Note on Fleury′s Algorithm

为了使用Ｆｌｅｕｒｙ的算法，在每一步都必须去判断图Ｇ－ｅ的连通性［１］。本文将给出一个十分简单的判断图的连通性的线性算法。为了证明它的正确性，本文将证明以下三个条件是等价的：（１）图Ｇ是连通的；（２）Ｍ的任意ｎ－１行都是线性无关的（这里Ｍ为图Ｇ的关联矩阵）；（３）在Ｍ中存在ｎ－１个线性无关的行。

To use Fleury′s algorithm, we must decide the connectivity of a graph G e for each step . In this paper, we will provide a very simple linear algorithm to decide the connectivity of graphs. To prove its correctness, the following conditions are prove to be equivalent:(1)Graph G is connective;(2) Any n-1 rows of M are linearly independent (where M is the incidence matrix of graph G );(3) There are n-1 linearly independent rows in M .