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

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

Characterization of Strongly Connected S2NS Signed Digraph

A strong sign nonsingular matrix (abbreviated S 2NS matrix) plays an important role in the study of qualitative matrix theory. In this paper, we study the problem about the characterizations of S 2NS signed digraphs which have close relationships with the S 2NS matrices. A signed digraph S is called a S 2NS signed digraph if each cycle of S is negative, and any two paths in S with the same initial vertex and the same terminal vertex have the same sign. We notice that there is no polynomial time algorithm for recognizing the two conditions in this definition. In this paper, we give a characterization of S 2NS signed digraphs for the strongly connected case for the first time, and all the conditions in this characterization can be checked by polynomial time algorithms.