|
|||||
|
|
| 关于Fleury算法的一点注记 | |
| 引用本文： | 吕义忠.关于Fleury算法的一点注记[J].南京航空航天大学学报,1998,30(4):470-472. |
| 作者姓名： | 吕义忠 |
| 作者单位： | 南京航空航天大学计算机科学与工程系 |
| 基金项目： | 国家自然科学基金,南京大学计算机重点实验室基金 |
| 摘 要： | 为了使用Ｆｌｅｕｒｙ的算法，在每一步都必须去判断图Ｇ－ｅ的连通性［１］。本文将给出一个十分简单的判断图的连通性的线性算法。为了证明它的正确性，本文将证明以下三个条件是等价的：（１）图Ｇ是连通的；（２）Ｍ的任意ｎ－１行都是线性无关的（这里Ｍ为图Ｇ的关联矩阵）；（３）在Ｍ中存在ｎ－１个线性无关的行。 |
| 关 键 词： | 图论 算法 数理逻辑 连通性 Fleury算法 |
| 本文献已被 CNKI 维普 等数据库收录！ | |