关于Fleury算法的一点注记

摘要

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