牟谷芳

（樂山師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，四川 樂山 614000）

有向通弦二部圖的最小秩問題研究

牟谷芳

（樂山師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，四川 樂山 614000）

有向二部圖的最小秩問題等價于研究與之對應(yīng)的符號模式矩陣的最小秩問題。文章研究了具有特殊結(jié)構(gòu)的有向通弦二部圖的最小秩問題，而獲得了有向通弦二部圖的最小秩為其團覆蓋數(shù)，并將有向二部圖的最小秩問題用于職場的雙選會中。

有向通弦二部圖；符號模式矩陣；最小秩

0 引言

無向圖和有向圖廣泛用于特殊矩陣的最小秩計算中。圖的最小秩問題最早是由P.M.Nylen[1]提出來的，他將實對稱矩陣與無向樹結(jié)合起來研究了實對稱矩陣的最小秩問題，并給出了求解方法的有效算法。由此，樹的最小秩問題就產(chǎn)生了。之后，S.M.Fallat和L.Hogben等人將無向樹的最小秩問題推廣到了一般無向圖的最小秩問題[2]。利用無向圖計算所有實對稱矩陣所對應(yīng)的對稱零-非零模式矩陣的最小秩。由此，將無向圖的最小秩問題自然推廣到了有向圖的最小秩問題，利用有向圖來研究實非對稱矩陣所對應(yīng)的非對稱零-非零模式矩陣的最小秩問題。由于利用代數(shù)方法計算特殊矩陣的最小秩較為困難，于是，通過圖的一些圖參數(shù)（路覆蓋數(shù) P(G)[2]，團覆蓋數(shù) CC(G)[2]，零迫集Z(G)[3]，圖的最小度數(shù)[4]，圖的最大匹配數(shù)match(G)[5]等）來確定圖的最小秩的下界或上界。在文獻[6]中，研究了無向通弦二部圖的最小秩問題，且獲得了無向通弦二部圖的最小秩為其團覆蓋數(shù)。在此基礎(chǔ)上，本文研究了特殊有向通弦二部圖的最小秩問題，且獲得了有向通弦二部圖的最小秩為其團覆蓋數(shù)，并將有向二部圖的最小秩問題應(yīng)用于職場的“雙選”中。

1 預(yù)備知識

下面介紹符號模式矩陣和有向通弦二部圖的一些重要定義。

定義1.1[7]設(shè)A=(aij)是一個n階實矩陣，以aij的符號{+，-，0}為元素所組成的矩陣稱為A的符號模式矩陣(Sign Pattern)，記為P。由與A有相同符號模式的所有實矩陣所組成的集合稱為由A所決定的定性矩陣類 (Qualitative Matrix Class)，記為。

定義1.2[8]設(shè)P是一個n階符號模式矩陣，P的最小秩定義為：

其中min表示最小值。

定義1.3[9]一個圖G由兩部分組成有限的非空頂點集V和邊集E。圖G的階數(shù)是G的頂點個數(shù)，記為|G|。一個若無重邊和環(huán)的圖稱為簡單圖。

定義1.4[9]一個有向圖是由非空有限集合V與集合E構(gòu)成，記為Γ，其中V中元素為頂點，E中元素為不同頂點的有序?qū)ΓQ為弧或有向邊。

定義1.5[9]在一個有向圖中，有向邊集{{i1，i2}，…{ik-1，ik}}的各個頂點都不同，稱從點i1到點ik的一條路（path），k為路的長度。若i1與 ik重合則稱{{i1，i2}，…{ik-1，ik}}為一個回路。

定義1.6[9]若圖G的頂點集V能夠被分為兩個子集U，V（稱為部集），使得 G的每條邊必然連接U中一個頂點和V中一個頂點（記G得邊集為E(G)），稱G為二部圖，記為G(U，V)。然而，這并不意味著U中每個頂點與V中每個頂點鄰接。

定義1.7[9]設(shè)M是E(G)的子集，如果M中任意兩條邊在G中均不鄰接，則稱M是G(U，V)的一個匹配，并記M所含的邊數(shù)為|M|。

定義 1.8[10]設(shè) G(U，V)為二部圖，P為一符號模式矩陣，其中，U={1，2，…，n}（對應(yīng) P的行標集）和 V={1′，2′，…，n′}（對應(yīng)P的列標集）。若圖G中的每邊都帶有符號，則稱G為符號圖，記為 G＝（V，E，sign），且 G（U，V）每邊的符號由P的符號來確定。若P中元素為正，則邊{i，j′}標為“+”，i∈U，j′∈V；若P中元素為負，則邊{i，j′}標為“-”，i∈U，j′∈V；若在 P中元素為零，在G(U，V)中不存在邊。

定義 1.9[10]設(shè) G(U，V)=(V，E，sign)為符號二部圖。若邊的符號為正，則有向邊{i，j′}∈E，i∈U，j′∈V；若邊的符號為負，則有向邊{j′，i}∈E，i∈U，j′∈V，G(U，V)稱為有向二部圖。

由有向圖的出度與入度的定義，我們給出了有向二部圖的出度與入度的定義。

定義 1.10 在有向二部圖 G(U，V)中(i∈U，j′∈V)，若（i，j′）∈E，為 G(U，V)的一條邊，則稱頂點j′是頂點i一個鄰接點；若邊{i，j′}的符號為正時，稱j′是i的一個“出度點”；若邊{i，j′}的符號為負時，j′是 i的一個“入度點”。頂點i的所有“出度點”的個數(shù)，稱為i的出度(out degree)，記為 deg+(i)；頂點 i的所有“入度點“的個數(shù)，稱為i的入度(in degree)，記為deg-(i)。

定義1.11[6]對于二部圖G(U，V)（部集為 U={1，2，…，n}和 V={1′，2′，…，n′}），若 U中的每一個頂點都和V中的每個頂點連接，則稱G(U，V)為完全二部圖 (complete bipartite graph)。

定義1.12[6]若二部圖中不含有長度為6或大于6的回路，稱為通弦(chordal bipartite)二部圖。

定義1.13[6]若二部圖能用r個完全二部子圖將G(U，V)的所有邊全部覆蓋，且 r最小，則稱 r為其團覆蓋數(shù)，記為bi(G(U，V))，其中，G(U，V)的團是其一個完全二部子圖。

根據(jù)定義1.12和定義1.13，給出有向完全二部圖和有向通弦二部圖的定義。

定義1.14對于有向二部圖G(U，V)（部集為 U={1，2，…，n}和 V={1′，2′，…，n′}），若 U中的每一個頂點都和V中的每個頂點連接，且U中的每一個頂點為出度點（或V中的每一個頂點為出度點），則稱G(U，V)為有向完全二部圖(directed complete bipartite graph)，若｜U｜=s，｜V｜=t有向完全二部圖可記為 Ks，t。

定義1.15 若有向二部圖中不含有長度為6或大于6的有向回路，稱為有向通弦(directed chordal bipartite)二部圖。

引理1.16[6]對任意帶有完美匹配M的通弦二部圖 G(U，V)，它的團覆蓋數(shù) bi(G(U，V))=｜M｜。

引理1.17[6]設(shè)G(U，V)是一個無向二部圖，則它的最小秩 mr(G(U，V))≤bi(G(U，V))。

引理1.18[6]設(shè)G(U，V)是一個無向通弦二部圖，則它的最小秩

2 有向通弦二部圖的最小秩

對于一般有向圖的最小秩問題目前還沒有很好的解決方法。近些年來，在符號圖的最小秩研究問題中，主要是研究特殊圖的最小秩計算方法和最小秩的上下界。本文在無向通弦二部圖的最小秩問題的研究基礎(chǔ)上，研究了有向通弦二部圖的最小秩問題，并將有向二部圖的最小秩應(yīng)用于實際問題中。

引理2.1 若有向二部圖G(U，V)為 n-有向回路，則 mr(G(U，V))=n-1。

證明：設(shè) G(U，V)為 n-有向回路，它所對應(yīng)的符號模式矩陣為

在P的行列展開式中有兩非零項，且符號不同，則mr(P)≠n，同時 P中含有一個 n-1階的下三角矩陣，則mr(P)=n-1，故有向二部圖G(U，V)的最小秩 mr(G(U，V))=n-1。

特別地，當k≤4時，G(U，V)為有向通弦二部圖，且它的最小秩為1。

引理 2.2 若有向二部圖 G(U，V)為 n階完全有向二部圖，則mr(G(U，V))=1。

證明：根據(jù)定義 1.14知，n階完全有向二部圖G(U，V)所對應(yīng)的符號模式矩陣各元素的符號都相同，則mr(G(U，V))=1。

定理2.3 設(shè)G(U，V)是一個有向二部圖，則它的最小秩 mr(G(U，V))≤bi(G(U，V))。

證明：設(shè) G(U，V)中的團覆蓋數(shù)為 r，構(gòu)建每一個團所對應(yīng)的符號模式矩陣Pi(i=1，2，..，r)，且每個矩陣的最小秩為1。再將這些矩陣相加得到一個新矩陣P，它所對的二部圖為G(U，V)，顯然 mr(P)≤r。故 G(U，V)的最小秩 mr(G(U，V))≤bi(G(U，V))。

定理2.4 設(shè)G(U，V)是一個有向二部團塊圖，且每個團圖為k-有向回路（k≤4）或為完全有向二部圖，則它的最小秩mr(G(U，V))=bi(G(U，V))。

證明：根據(jù)引理2.1和引理2.2知，mr(G(U，V))≥bi(G(U，V))再由定理2.3 可得 mr(G(U，V))=bi(G(U，V))。

定理2.5 在一個有向通弦二部圖G(U，V)中，若 G(U′，V′)是 G(U，V)中帶有唯一完美匹配M′的最大子圖，則

證明：若 G(U′，V′)=G(U，V)，結(jié)論顯然成立。

若 G(U′，V′)≠G(U，V)，首先尋找 G(U，V)中的通弦二部子圖K2.2，設(shè)團數(shù)為r。然后刪除這些團，得二部圖為G(U″，V″)。利用文獻[10]算法3.1尋找?guī)в形ㄒ煌昝榔ヅ銶″的最大子圖，則｜M′｜=｜M″｜+r。

根據(jù)引理2.2和定理2.4，結(jié)論成立。

3 應(yīng)用

圖的最小秩問題廣泛應(yīng)用于通信網(wǎng)絡(luò)和信息科學(xué)中[11-12]，尤其在通信復(fù)雜度上有重要應(yīng)用，如在文獻[11]中，利用符號模式的最小秩確定了通信復(fù)雜度的一個下界。本節(jié)將通弦二部圖的最小秩問題應(yīng)用于職場招聘會的雙選中。

例3.1 設(shè)有5位大學(xué)畢業(yè)生：A1，A2，A3，A4，A5，某企業(yè)公開招聘的崗位有顧問，編輯，程序員，秘書，培訓(xùn)師五個崗位。為了方便后面的敘述，將畢業(yè)生與不同崗位進行編號：A1，A2，A3，A4，A5，分別對應(yīng) 1，2，3，4，5；顧問，編輯，程序員，秘書，培訓(xùn)師分別對應(yīng) 1′，2′，3′，4′，5′。在職場招聘會上，不同的畢業(yè)生和各個崗位對應(yīng)的情況如下：

1∶2′，3′；2∶1′，2′，4′，5′；3∶2′，3′；4∶2′，3′；5∶4′，5′。

假設(shè)每個崗位只招一人，試問每個畢業(yè)生是否能夠挑選到合適的工作？

圖1 二部圖G(U，V)

圖2 G(U，V)的完美匹配

方案：畢業(yè)生與崗位對應(yīng)的情況利用二部圖G(U，V)（如圖1所示）來建立模型，其中U={1，2，3，4，5}，V={1′，2′，3′，4′，5′}。容易判斷G(U，V)是無向通弦二部圖，且團覆蓋數(shù)為3。由引理2.2知，G(U，V)的最小秩為3。因此，至少有3位畢業(yè)生能找到合適工作。但是圖1中的完美匹配不是唯一的，故不是每個人都能夠找到合適的工作。

根據(jù)文獻[10]算法3.1，在圖3中能夠找到一個最大唯一完美匹配（如圖2所示）：

M′∶{{1，2′}，{2，1′}，{3，3′}，{5，5′}}。

因此，A1，A2，A3，A5 能找到合適的崗位，且分別對應(yīng)的崗位為編輯，顧問，程序員，培訓(xùn)師。

在工作崗位招聘過程中，不僅畢業(yè)生想要挑選一份滿意的工作，而且工作崗位對畢業(yè)生也有不同的要求，比如英語水平、計算機等級水平和專業(yè)技術(shù)水平等因素，工作崗位也要挑合適的人選，即為校園招聘“雙選會”。因此，我們將有向通弦二部圖的最小秩問題應(yīng)用于職場“雙選會”的研究中。

例3.2 設(shè)有4位大學(xué)畢業(yè)生：A1，A2，A3，A4，某企業(yè)公開招聘的崗位有編輯，程序員，秘書，培訓(xùn)師4個崗位。將畢業(yè)生與不同崗位進行編號：A1，A2，A3，A4，分別對應(yīng)1，2，3，4；編輯，程序員，秘書，培訓(xùn)師分別對應(yīng) 1′，2′，3′，4′。在職場招聘會上，不同的畢業(yè)生挑選不同崗位的情況如下：

1∶1′，2′，3′，4′；2∶1′，3′；3∶1′，2′；4∶1′，4′。

反之，不同的工作崗位挑選不同人選的情況如下：

2′∶2，4；3′∶3，4；4′∶2，3。

假設(shè)每個崗位只招一人，試問每個畢業(yè)生是否能夠挑選到合適的工作？ 反之，工作崗位能否招到合適的人員？

圖3 有向二部圖G(U，V)

圖4 有向二部子圖G(U1，V1)

方案：畢業(yè)生與崗位對應(yīng)的情況利用有向二部圖G(U，V)（如圖3所示）來建立模型，其中 U={1，2，3，4，}，V={1′，2′，3′，4′}。與 G(U，V)所對應(yīng)的符號模式矩陣為

將P用于職場“雙選會”的研究中，可以從如下兩個方面來考慮。

一方面考慮每個畢業(yè)生能否挑選到自己滿意的工作。

根據(jù)畢業(yè)生挑選的崗位情況 1∶1′，2′，3′，4′；2∶1′，3′；3∶1′，2′；4∶1′，4′可知，在有向二部圖G(U，V)中不能夠找到一個最大唯一完美匹配。因此，不是每個人能夠找到合適的工作。若在G(U，V)的U和 V中分別刪除頂點1和 1′，得到子圖G(U1，V1)（見圖4）。在G(U1，V1)中能夠找到一個最大唯一完美匹配（如圖5所示）：

M′＝{{2，3′}，{3，2′}，{4，4′}}。

因此，A2，A3，A4能找到合適的崗位，且分別對應(yīng)的崗位為秘書，程序員，培訓(xùn)師。

圖5 最大完美匹配

圖6 最大完美匹配

另一方面考慮每個工作崗位能否挑選到合適的人選。

根據(jù)畢業(yè)生挑選的崗位情況 2′∶2，4；3′∶3，4；4′∶2，3 可知，在有向二部圖 G(U1，V1)中能夠找到一個最大唯一完美匹配（如圖6所示）：

M″∶{{2′，4}，{3′，3}，{4′，2}}。

因此，培訓(xùn)師，秘書，程序員能找到合適的人選，且分別對應(yīng)的人選為A2，A3，A4。

容易判斷G(U，V)是有向通弦二部圖，且團覆蓋數(shù)為3。由定理2.4知，G(U，V)的最小秩為3。因此，有3位畢業(yè)生能找到合適工作和3個崗位能夠找到合適的人員。

（本文部分內(nèi)容系筆者2015年電子科技大學(xué)博士畢業(yè)論文《矩陣完備化和圖的最小秩問題》）

[1]NYLEN P M.Minimum-rank matrices with prescribed graph[J].Linear Algebra Appl.，1996，248：303-316.

[2]FALLAT S M，統(tǒng) HOGBEN L.Theminimum rank of symmetric matrices described by a graph：a survey[J].Linear Algebra Appl.，2007，426:558-582.

[3]HOGBEN L.Minimum rank problems[J].Linear Algebra Appl.，2010，432:1961-1974.

[4]AIM Minimum Rank-Special Graphs Work Graph.Zero forcing sets and theminimum rank of graphs[J].Linear Algebra Appl.，2008，428：1628-1648.

[5]IMA-ISU Research Group.Minimum rank of skew-symmetric matrices described by a graph[J].Linear Algebra Appl.，2009，432：2457-2472.

[6]JOHNSON C R，MILLER J.Rank decomposition under combinatorial constraints[J].Linear Algebra&Its Applications，1997，251：97-104.

[7]DEALBA L M，HARDY T L，HENTZEL I R，et al.Minimum rank and maximum eigenvalue multiplicity of symmetric tree sign patterns[J].Linear Algebra Appl.，2006，418：389-415.

[8]LI Z S，GAO Y B，ARAV M，et al.Sign patterns withminimum rank two and upper boundsonminimum ranks[J].Linear Multilinear A.，2014，61：895-908.

[9]張先迪，李正良.圖論及其應(yīng)用[M].北京：高等教育出版社，2005：2.

[10]牟谷芳，黃廷祝.符號有向圖的最大SNS-符號模式矩陣[J].工程數(shù)學(xué)學(xué)報，2015（5）：772-782.

[11]BURGARTH D，ALESSANDRO D D，HOGBEN L.Zero forcing，linear and quantum controllability for systems evolving on networks[J].Automatic Control，IEEE Transactions on，2013，58:773-784.

[12]LINIAL N，MENDELSON S，SCHECHTMAN G，et al.Complexity measures of sign matrices[J].Combinatorica，2007，27：439-463.

The Minimum Rank Problem Research of Directed Chordal Bipartite Graph

MU Gufɑnɡ
（School of Mathematics and Information Science,Leshan Normal University,Leshan Sichuan 614000,China）

Theminimum rank problem of directed bipartite graph is equivalent to the correspondingminimum rank problem of symbolic pattern matrix.In this paper，theminimum rank problem of directed chordal bipartite graph with a special structure has been studied.In this case,theminimum rank of a directed chordal bipartite graph is its clique coverage number.Beside，theminimum rank problem of directed chordal bipartite graph is used in job fair based on mutual selection.

Directed Chordal Bipartite Graph；Symbolic Pattern Matrix；Minimal Rank

O157.6

A

1009-8666（2017）08-0005-06

［責(zé)任編輯、校對：李書華］

10.16069/j.cnki.51-1610/g4.2017.08.002

2017-04-13

四川省教育廳資助科研項目“有向圖的最小秩問題及其在通信網(wǎng)絡(luò)中的應(yīng)用”（17ZB0193）；樂山師范學(xué)院資助科研項目“有向圖的最小秩問題及其應(yīng)用”（Z1521)

牟谷芳（1981—），女，土家族，湖北恩施人。樂山師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院講師，博士，研究方向：組合矩陣論。