关于有向图的强符号可解性

Hansen已提出一个判别强符号可解有向图的一般算法,其时间复杂性为O(mn).仔细分析算法,尚存在很多重复过程而耗费时间。从图论的观点看,最有效的算法应当是O(m)。本文进一步研究强符号可解有向图的一些基本性质,在此基础上发现这类图存在一种嵌套结构。结合有向图的DFS纵深搜索法,我们找到一个最有效的递推算法,其时间复杂性恰为O(m)。从而,使符号有向图的判别问题满意地获得解决。

关于矩阵广义逆符号模式的若干性质

若一个实矩阵A的广义逆A+的符号模式由A的符号模式所唯一确定 ,则A被称为广义逆符号唯一 .在关于广义逆符号唯一矩阵的一些现有结论基础上 ,进一步研究了当矩阵A为广义逆符号唯一时 ,A+的符号模式和零位模式的具体特征 .还讨论了当A不为广义逆符号唯一时 ,与A有相同符号模式的矩阵广义逆族在某些位置上所能取到的不同符号情况 ,并且给出了这一结果在讨论线性方程组的最小二乘符号可解性中的一个应用 .