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

Construction of Minimal Forbidden Configuration with Odd Number of Strong Components

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

The characterization and construction of minimal forbidden configuration(MFC) of strong sign nonsingular digraph (simplifed as S 2NS digraph) are concerned by many researchers.All the examples of MFC known up to now have even number of strong components.So,in the paper 《On digraphs and forbidden configurations of strong sign nonsingular matrices》,the author proposed a supposition whether any MFC must be with even number of strong components.This article constructs infinitely many MFCs that have odd number of strong components by making changes to a graph with special structure on the basement of a new MFC which has been constructed in this paper,thus solves the problem.