牟谷芳

（乐山师范学院 数学与信息科学学院，四川 乐山 614000）

有向通弦二部图的最小秩问题研究

牟谷芳

（乐山师范学院 数学与信息科学学院，四川 乐山 614000）

有向二部图的最小秩问题等价于研究与之对应的符号模式矩阵的最小秩问题。文章研究了具有特殊结构的有向通弦二部图的最小秩问题，而获得了有向通弦二部图的最小秩为其团覆盖数，并将有向二部图的最小秩问题用于职场的双选会中。

有向通弦二部图；符号模式矩阵；最小秩

0 引言

无向图和有向图广泛用于特殊矩阵的最小秩计算中。图的最小秩问题最早是由P.M.Nylen[1]提出来的，他将实对称矩阵与无向树结合起来研究了实对称矩阵的最小秩问题，并给出了求解方法的有效算法。由此，树的最小秩问题就产生了。之后，S.M.Fallat和L.Hogben等人将无向树的最小秩问题推广到了一般无向图的最小秩问题[2]。利用无向图计算所有实对称矩阵所对应的对称零-非零模式矩阵的最小秩。由此，将无向图的最小秩问题自然推广到了有向图的最小秩问题，利用有向图来研究实非对称矩阵所对应的非对称零-非零模式矩阵的最小秩问题。由于利用代数方法计算特殊矩阵的最小秩较为困难，于是，通过图的一些图参数（路覆盖数 P(G)[2]，团覆盖数 CC(G)[2]，零迫集Z(G)[3]，图的最小度数[4]，图的最大匹配数match(G)[5]等）来确定图的最小秩的下界或上界。在文献[6]中，研究了无向通弦二部图的最小秩问题，且获得了无向通弦二部图的最小秩为其团覆盖数。……