强连通强符号非异带号有向图的特征刻画

强符号非异矩阵 (简称S2 NS矩阵 )在定性矩阵理论的研究中有重要意义 .据此研究与S2 NS矩阵直接相关的S2 NS带号有向图的特征刻画问题 .一个带号有向图S称为是S2 NS带号有向图 ,若S中所有圈的符号均为负 ,且S中任意两条同始同终的路均同号 .注意到在此定义中所涉及到的两个条件都不能用多项式算法来进行验证 .这里首次给出强连通情况下S2

含奇数个强分支的S^2NS极小禁用子图的构造

强符号非异有向图 (简称S2 NS有向图 )的极小禁用子图 (简称MFC)的判定和构造等问题是众多学者所关心的问题 .迄今为止的所有已知的MFC都恰好含有偶数个强连通分支 .在文献《对强符号非奇性矩阵的有向图和禁用图的研究》中提出一个问题 ,是否MFC必定含有偶数个强分支 .为此通过对一个具有特殊结构的图进行变化得到一个恰含奇数个强分支的MFC ,再以这个新的MFC为基础构造了无穷多的含奇数个强分支的MFC 。