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

Characterization of Strongly Connected S^2NS Signed Digraph

作　　者：吴群[1] 邵嘉裕[1] 

机构地区：[1]同济大学应用数学系,上海200092

出　　处：《同济大学学报（自然科学版）》2000年第2期201-205,共5页Journal of Tongji University:Natural Science

基　　金：国家自然科学基金资助项目! ( 198310 50 );上海市科技发展基金资助项目! ( 97XD14 0 0 8)

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

关 键 词：强符号非异矩阵 强连通强符号非异号有向图 特征刻画 符号模式 圈 多项式算法 

分 类 号：O157.5[理学—数学]