在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2015, Vol. 32 ›› Issue (5): 772-782.doi: 10.3969/j.issn.1005-3085.2015.05.014

• • 上一篇    下一篇

符号有向图的最大SNS-符号模式矩阵(英)

牟谷芳1,2,   黄廷祝1   

  1. 1- 电子科技大学数学科学学院，成都 611731
    2- 乐山师范学院数学与信息科学学院，乐山 614000
  • 收稿日期:2015-01-15 接受日期:2015-06-04 出版日期:2015-10-15 发布日期:2015-12-15
  • 基金资助:
    国家自然科学基金  (61170309).

The Maximal SNS-pattern Matrix for a Signed Digraph

MOU Gu-fang1,2,   HUANG Ting-zhu1   

  1. 1- School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 611731
    2- College of Mathematics and Information Science, Leshan Normal University, Leshan 614000
  • Received:2015-01-15 Accepted:2015-06-04 Online:2015-10-15 Published:2015-12-15
  • Supported by:
    The National Natural Science Foundation of China (61170309).

PDF (PC)

10

摘要： 对于非对称符号模式矩阵$P$，可借助于符号有向图来分析符号模式矩阵$P$的符号特征．符号有向图的最大SNS-符号模式矩阵是非对称符号模式矩阵$P$的最大非奇矩阵．符号二部图为研究符号有向图的最大SNS-符号模式矩阵和最小秩提供了一个新的途径．本文将符号有向图转换为符号二部图$G(U,V)$，并提出了构造$G(U,V)$的最大子图的算法：一是在$G(U',V')$中寻求最大完美匹配$M'$；二是寻求含有偶数个$e$-圈且不相交的$M'$-交替圈．通过算法而构造了符号有向图的SNS-符号模式矩阵．

关键词: SNS-符号模式矩阵, 符号有向图, 符号二部图, 匹配, 行列式

Abstract:

For an asymmetric sign pattern matrix $P$, we analyze the sign characteristic of $P$ with the help of a signed digraph in this paper. The maximal SNS-pattern matrix for a signed digraph is the maximal sign-nonsingular sub-pattern among all real matrices having the given sign pattern $P$. In this paper, SNS problems for signed digraphs are studied by converting a signed digraph $\Gamma$ into a signed bipartite graph $G(U,V)$. We propose the algorithms for searching for a sub-signed bipartite graph $G(U',V')$ with the maximum perfect matching $M'$ corresponding to every set of disjoint $M'$-interlacing cycles, which contain an even number of $M'$-interlacing $e$-cycles. The maximal SNS-pattern for a signed digraph is obtained according to algorithms.

Key words: SNS-pattern matrix, signed digraph, signed bipartite graph, matching, determinant

中图分类号: