邊轉(zhuǎn)換與增加對有向網(wǎng)絡(luò)能控性的影響

張虎林　李成鐵　王立夫

摘要： 復(fù)雜網(wǎng)絡(luò)的不同類型邊轉(zhuǎn)換（方向改變）和在不同節(jié)點間增加邊對網(wǎng)絡(luò)能控性有不同影響，為了更好地了解有向網(wǎng)絡(luò)邊轉(zhuǎn)換和增加對網(wǎng)絡(luò)能控性影響，提出一種邊分類方法，把邊根據(jù)節(jié)點類別和匹配關(guān)系分成12種類型，并給出辨識算法?；诖朔诸惤o出網(wǎng)絡(luò)邊轉(zhuǎn)換和增加時網(wǎng)絡(luò)能控性（驅(qū)動節(jié)點數(shù)目）的變化規(guī)律。通過模型網(wǎng)絡(luò)和實際網(wǎng)絡(luò)分析了每種邊在網(wǎng)絡(luò)中的比例，并分析了邊轉(zhuǎn)換和增加時驅(qū)動節(jié)點數(shù)目變化。結(jié)果驗證了定理的正確性。

關(guān)鍵詞： 網(wǎng)絡(luò)能控性;驅(qū)動節(jié)點;最大匹配;轉(zhuǎn)換邊;增加邊

中圖分類號： N94文獻(xiàn)標(biāo)識碼： A

Influence of Alteration and Addition of Edges on Directed Network Controllability

ZHANG Hulin， LI Chengtie， WANG Lifu

Abstract：The alternation of different types of edges （direction changed） and the addition of edges between different nodes in complex networks will have different effect on the controllability of the network. In order to better understand the influence of altering different edges and adding different edges on network controllability in directed networks， this paper proposes a classification method of edges. According to the node category and matching relationship， the directed edges are divided into twelve types， and the algorithm of identification is given. Based on the classification， the change law of network controllability （the number of driving nodes） is given when the edges of networks are altered and added. Through the simulation experiment of the model networks and the actual networks， the proportion of different types of edges is analyzed. When edges are altered and added， the changes in the number of driven nodes are analyzed in the model networks and the actual networks. The correctness of the theorems of this article are verified.

Key words： network controllability; driver node; maximum matching; alteration of edges; addition of edges

0 引言

近些年來，隨著網(wǎng)絡(luò)科學(xué)的發(fā)展，人們發(fā)現(xiàn)各種復(fù)雜系統(tǒng)（相互作用和依賴的各部分組成的具有特定功能的整體）可以由節(jié)點和連邊組成的網(wǎng)絡(luò)來表示，其中網(wǎng)絡(luò)中各節(jié)點表示系統(tǒng)的各個組成部分，節(jié)點間的邊表示各組成部分的相互作用和依賴關(guān)系。例如，計算機(jī)網(wǎng)絡(luò)［1］可以看成由很多獨立工作的計算機(jī)通過傳輸介質(zhì)相連而成的網(wǎng)絡(luò)［1］，其中獨立工作的計算機(jī)看作節(jié)點，傳輸介質(zhì)看作節(jié)點間的連邊；電力網(wǎng)絡(luò)［2-3］可以看作由各個變電站通過電纜連接而成的網(wǎng)絡(luò)，其中變電站看作節(jié)點，電纜看作連接節(jié)點間的連邊。類似的還有交通網(wǎng)絡(luò)［4］和生物網(wǎng)絡(luò)［5］等。

研究復(fù)雜網(wǎng)絡(luò)［6-7］的最終目的是尋找有效的控制手段控制網(wǎng)絡(luò)行為。從經(jīng)典控制理論可知，控制網(wǎng)絡(luò)行為的前提是該網(wǎng)絡(luò)必須是完全能控的，因此研究復(fù)雜網(wǎng)絡(luò)能控性具有重要的理論意義。此外，復(fù)雜網(wǎng)絡(luò)能控性的研究也具有重要的現(xiàn)實意義。例如，在基因調(diào)控網(wǎng)絡(luò)［8］中，選擇哪些基因作為藥物靶點，能使整個生物網(wǎng)絡(luò)達(dá)到預(yù)期狀態(tài)；在社交網(wǎng)絡(luò)里［9］，選擇哪些平臺發(fā)布信息，能使信息的傳播達(dá)到期望結(jié)果。很多實際網(wǎng)絡(luò)都涉及復(fù)雜網(wǎng)絡(luò)能控性問題。

為使復(fù)雜網(wǎng)絡(luò)完全能控，將線性系統(tǒng)能控性理論應(yīng)用到復(fù)雜網(wǎng)絡(luò)。2011年，Liu等［10］提出一種求解復(fù)雜網(wǎng)絡(luò)能控性所需的最少驅(qū)動節(jié)點數(shù)目的方法，該方法采用圖論的匹配定理［11-12］，將復(fù)雜網(wǎng)絡(luò)的能控性問題轉(zhuǎn)換為有向網(wǎng)絡(luò)的最大匹配問題，從而建立關(guān)于復(fù)雜網(wǎng)絡(luò)可控性的理論研究框架。然而對于無向網(wǎng)絡(luò)的能控性問題該方法并不適用。因此，Yuan等［13］通過采用PBH能控性判據(jù)提出復(fù)雜網(wǎng)絡(luò)精確能控性的理論框架，可求解有邊權(quán)重和任意結(jié)構(gòu)網(wǎng)絡(luò)的能控性。基于這兩個框架，許多學(xué)者對時變網(wǎng)絡(luò)能控性［14］，多層網(wǎng)絡(luò)能控性［15］，對稱網(wǎng)絡(luò)結(jié)構(gòu)能控性［16］等方面進(jìn)行了深入研究。

隨著研究的深入，人們發(fā)現(xiàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對復(fù)雜網(wǎng)絡(luò)的能控性有重要影響。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化分為節(jié)點或邊的變化，其中節(jié)點的變化會造成邊數(shù)目的變化，邊的變化不會造成節(jié)點數(shù)目的變化。因此邊的變化對網(wǎng)絡(luò)能控性的變化更易判斷，而目前邊變化的研究包括邊變換對網(wǎng)絡(luò)能控性優(yōu)化和邊的失效。對于邊變換對網(wǎng)絡(luò)能控性優(yōu)化主要從以下3種方法考慮［17］：增加邊［18-22］、交換邊［23］、轉(zhuǎn)換邊（改變邊的方向）［24-26］。Zhang等［21］提出了一種增加邊的算法，利用給出的最小生成森林使網(wǎng)絡(luò)加邊的成本最小，該算法使網(wǎng)絡(luò)增加邊的數(shù)目最少并實現(xiàn)網(wǎng)絡(luò)的結(jié)構(gòu)能控。Wang等［22］給出一種網(wǎng)絡(luò)加邊的優(yōu)化算法，該算法將介數(shù)中心性作為網(wǎng)絡(luò)加邊的成本，使加邊成本最小且實現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)能控。Rong等［23］提出一種在保持度分布不變的約束下重新布線的算法，該算法可改變網(wǎng)絡(luò)能控性并提高網(wǎng)絡(luò)的魯棒性。Hou等［24］提出一種基于匹配邊的節(jié)點和邊的分類方法，在此基礎(chǔ)上提出一種轉(zhuǎn)換邊的算法，該算法通過局部信息來改變網(wǎng)絡(luò)的能控性，而且網(wǎng)絡(luò)的優(yōu)化成本大幅度降低，比如電力網(wǎng)絡(luò)［27］。對于邊的失效，Hao等［28］根據(jù)節(jié)點和無標(biāo)度網(wǎng)絡(luò)的特征，提出了14種基于兩條邊重要性函數(shù)的邊攻擊策略，使網(wǎng)絡(luò)能控性降低。Lou等［29］給出一種邊的分類方法，根據(jù)該邊的分類對網(wǎng)絡(luò)的邊進(jìn)行攻擊，從而實現(xiàn)網(wǎng)絡(luò)能控性改變。此外，還有許多研究通過邊的變化改變網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，從而對網(wǎng)絡(luò)能控性造成影響。

綜上所述，發(fā)現(xiàn)當(dāng)前通過邊的變化實現(xiàn)對網(wǎng)絡(luò)能控性影響的研究主要集中在邊失效對網(wǎng)絡(luò)能控性影響和邊變換對網(wǎng)絡(luò)能控性優(yōu)化上，并未從理論層面出發(fā)，給出轉(zhuǎn)換邊和增加邊對網(wǎng)絡(luò)能控性的影響。對于整個復(fù)雜網(wǎng)絡(luò)，哪些邊轉(zhuǎn)換或在哪些節(jié)點間增加邊能改變網(wǎng)絡(luò)能控性，哪些邊轉(zhuǎn)換對網(wǎng)絡(luò)能控性沒有影響，至今沒有明確的結(jié)論。因此，本文為了對此問題進(jìn)行研究，將網(wǎng)絡(luò)中邊進(jìn)行分類，并從理論層面給出不同邊變換對網(wǎng)絡(luò)能控性影響的確切結(jié)論。首先根據(jù)節(jié)點類型和邊的匹配關(guān)系提出一種有向網(wǎng)絡(luò)的邊分類方式，給出邊辨識算法，然后研究了有向網(wǎng)絡(luò)中邊轉(zhuǎn)換和節(jié)點間增加邊對網(wǎng)絡(luò)能控性的影響，最后通過模型網(wǎng)絡(luò)和實際網(wǎng)絡(luò)仿真，分析了不同類型邊在網(wǎng)絡(luò)中的占比并驗證了轉(zhuǎn)換邊和增加邊定理的有效性。

1 復(fù)雜網(wǎng)絡(luò)能控性

考慮一個N個節(jié)點的復(fù)雜網(wǎng)絡(luò)，其動力學(xué)方程表示為

（1）

其中，x（t）=［x1，x2，…，xN］T表示網(wǎng)絡(luò)中節(jié)點的狀態(tài)，xj（t）表示第j個節(jié)點在t時刻時的狀態(tài)，A=［aij］∈RN×N為網(wǎng)絡(luò)的鄰接矩陣，其中aij代表節(jié)點j作用到節(jié)點i的強(qiáng)度，aij＞0表示積極作用，aij＜0表示消極作用，aij=0表示節(jié)點j與節(jié)點i無連接關(guān)系，即節(jié)點j不作用到節(jié)點i；u（t）=［u1，u2，…，uM］T表示M個輸入控制信號在t時刻的輸入量；B∈RN×M稱為輸入矩陣，B表示外部輸入節(jié)點與內(nèi)部節(jié)點的耦合關(guān)系，bij表示輸入信號uj（t）與節(jié)點i之間的耦合關(guān)系。

對于復(fù)雜網(wǎng)絡(luò)系統(tǒng)（1），若存在一個分段連續(xù)的u（t），可在有限的時間［t0，tf］內(nèi)從任意初始狀態(tài)x（t0）驅(qū)動到任何期望的最終狀態(tài)x（tf），則稱此系統(tǒng)的狀態(tài)是完全能控的。在控制理論中，通過卡爾曼判據(jù)判斷系統(tǒng)是否完全能控，系統(tǒng)（1）完全能控當(dāng)且僅當(dāng)能控性矩陣C=［B，AB，…，AN-1B］是滿秩的，即rank（C）=N。因此要使一個給定網(wǎng)絡(luò)能控，則需要尋找一個輸入矩陣B使得能控性矩陣C滿秩。當(dāng)復(fù)雜網(wǎng)絡(luò)節(jié)點間不考慮連接強(qiáng)度時，即不考慮矩陣A與B具體權(quán)值，僅考慮矩陣中的元素是零或獨立自由參數(shù)，這時矩陣A與B稱為結(jié)構(gòu)化矩陣。如果存在A與B中一組非零值，使得網(wǎng)絡(luò)是能控的，則稱系統(tǒng)（1）為結(jié)構(gòu)能控，也可記為（A，B）結(jié)構(gòu)能控。根據(jù)有向邊的方向，在下文中將邊的起始節(jié)點稱為頭節(jié)點，邊的結(jié)束節(jié)點稱為尾節(jié)點。

對于有向復(fù)雜網(wǎng)絡(luò)G=（V，E），其中V和E為網(wǎng)絡(luò)的節(jié)點集和邊集。如果網(wǎng)絡(luò)邊集E的一個子集M中沒有兩條邊共享一個公共的頭節(jié)點或尾節(jié)點，則M稱為G的一個匹配。G中邊數(shù)最多的匹配稱為G的最大匹配。最大匹配一般是非唯一的，可由Hopcroft-Karp算法［30］得到。如果一個節(jié)點是匹配中某條邊的尾節(jié)點，則該節(jié)點為匹配節(jié)點，否則為非匹配節(jié)點。對于網(wǎng)絡(luò)節(jié)點i，從網(wǎng)絡(luò)中其他節(jié)點指向節(jié)點i的邊數(shù)目是節(jié)點i的入度，節(jié)點i指向其他節(jié)點的邊數(shù)目是節(jié)點i的出度。

Liu等［10］把圖論中匹配理論與結(jié)構(gòu)能控性相結(jié)合，給出一種求解最小驅(qū)動節(jié)點集分析復(fù)雜網(wǎng)絡(luò)能控性的理論框架，并給出最小輸入定理，證明了實現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)能控所需獨立控制的節(jié)點集合等于非最大匹配的節(jié)點集合，其中需要被不共享輸入信號控制的節(jié)點稱為網(wǎng)絡(luò)的驅(qū)動節(jié)點，驅(qū)動節(jié)點數(shù)目用ND表示，使得網(wǎng)絡(luò)結(jié)構(gòu)能控所需的最小驅(qū)動節(jié)點集合為最小驅(qū)動節(jié)點集（Minimum Driven Node Set，簡稱MDS），通過對MDS中節(jié)點施加外部輸入控制信號可使控制信息傳達(dá)到網(wǎng)絡(luò)中每一個節(jié)點，實現(xiàn)整個網(wǎng)絡(luò)的完全能控。

引理1 最小輸入定理［10］：控制有向網(wǎng)絡(luò)G的最小輸入節(jié)點數(shù)NI與最小驅(qū)動節(jié)點數(shù)目ND等價。若有向網(wǎng)絡(luò)G存在完全匹配，NI等于1并且網(wǎng)絡(luò)中任意一個節(jié)點可作驅(qū)動節(jié)點；否則，NI等于網(wǎng)絡(luò)中最大匹配后沒有被匹配的節(jié)點數(shù)。用式（2）表示：

（2）

其中，N為有向網(wǎng)絡(luò)中節(jié)點數(shù)目，|M|為網(wǎng)絡(luò)中最大匹配節(jié)點數(shù)目。

網(wǎng)絡(luò)的能控性nD的大小由網(wǎng)絡(luò)所需的最小驅(qū)動節(jié)點數(shù)與網(wǎng)絡(luò)節(jié)點總數(shù)的比值來計算，即nD=ND/N，nD的大小表示該網(wǎng)絡(luò)被控的難易程度，nD越小，網(wǎng)絡(luò)越易被控制，nD越大，網(wǎng)絡(luò)越難被控制。

有向網(wǎng)絡(luò)中，若實現(xiàn)網(wǎng)絡(luò)完全能控，需對個數(shù)固定的未匹配節(jié)點進(jìn)行控制。但是由于一個網(wǎng)絡(luò)存在多組不同最大匹配，使網(wǎng)絡(luò)有很多不同的MDS。根據(jù)節(jié)點參與MDS的程度，將節(jié)點分為三類，定義［31］如下：

定義1 如果一個節(jié)點參與全部的MDS，則這個節(jié)點為關(guān)鍵節(jié)點；如果一個節(jié)點不全參與全部的MDS，則這個節(jié)點為間歇節(jié)點；如果一個節(jié)點不參與任何一個MDS，則這個節(jié)點為冗余節(jié)點。

對于圖1d網(wǎng)絡(luò)，存在3組最大匹配和MDS，如圖1a、1b和1c所示。其中節(jié)點1參與全部MDS，故為關(guān)鍵節(jié)點；節(jié)點2不參與任何一個MDS，故為冗余節(jié)點；節(jié)點3，4，5參與部分MDS，故為間歇節(jié)點。

2 邊分類及類型辨識

2.1 邊的分類方式

有向網(wǎng)絡(luò)中，節(jié)點的類型有所不同，節(jié)點間通過有向邊連接，網(wǎng)絡(luò)中邊的最大匹配也是非唯一的，故參與最大匹配的邊也存在不同。根據(jù)邊匹配關(guān)系與邊兩端節(jié)點的類型將邊進(jìn)行分類。

類型1 關(guān)鍵輸出完全匹配和冗余輸入完全匹配邊：如果該邊的頭節(jié)點為關(guān)鍵節(jié)點，尾節(jié)點為冗余節(jié)點，并且該邊參與全部最大匹配，則這個邊稱為關(guān)鍵輸出完全匹配和冗余輸入完全匹配邊（Critical Output Matching and Redundant Input Matching，簡稱COM-RIM）。

類型2 間歇輸出完全匹配和冗余輸入完全匹配邊：如果該邊的頭節(jié)點為間歇節(jié)點，尾節(jié)點為冗余節(jié)點，并且該邊參與全部最大匹配，則這個邊稱為間歇輸出完全匹配和冗余輸入完全匹配邊（Intermittent Output Matching and Redundant Input Matching，簡稱IOM-RIM）。

類型3 冗余輸出完全匹配和冗余輸入完全匹配邊：如果該邊的頭節(jié)點為冗余節(jié)點，尾節(jié)點為冗余節(jié)點，并且該邊參與全部最大匹配，則這個邊稱為冗余輸出完全匹配和冗余輸入完全匹配邊（Redundant Output Matching and Redundant Input Matching，簡稱ROM-RIM）。

類型4 關(guān)鍵輸出不完全匹配和冗余輸入不完全匹配邊：如果該邊的頭節(jié)點為關(guān)鍵節(jié)點，尾節(jié)點為冗余節(jié)點，并且該邊參與部分最大匹配，則這個邊稱為關(guān)鍵輸出不完全匹配和冗余輸入不完全匹配邊（Critical Output No Perfect Matching and Redundant Input No Perfect Matching，簡稱COOPM-RIOPM）。

類型5 間歇輸出不完全匹配和冗余輸入不完全匹配邊：如果該邊的頭節(jié)點為間歇節(jié)點，尾節(jié)點為冗余節(jié)點，并且該邊參與部分最大匹配，則這個邊稱為間歇輸出不完全匹配和冗余輸入不完全匹配邊（Intermittent Output No Perfect Matching and Redundant Input No Perfect Matching，簡稱IOOPM-RIOPM）。

類型6 冗余輸出不完全匹配和冗余輸入不完全匹配邊：如果該邊的頭節(jié)點為冗余節(jié)點，尾節(jié)點為冗余節(jié)點，并且該邊參與部分最大匹配，則這個邊稱為冗余輸出不完全匹配和冗余輸入不完全匹配邊（Redundant Output No Perfect Matching and Redundant Input No Perfect Matching，簡稱ROOPM-RIOPM）。

類型7 關(guān)鍵輸出不完全匹配和間歇輸入不完全匹配邊：如果該邊的頭節(jié)點為關(guān)鍵節(jié)點，尾節(jié)點為間歇節(jié)點，并且該邊參與部分最大匹配，則這個邊稱為關(guān)鍵輸出不完全匹配和間歇輸入不完全匹配邊（Critical Output No Perfect Matching and Intermittent Input No Perfect Matching，簡稱COOPM-IIOPM）。

類型8 間歇輸出不完全匹配和間歇輸入不完全匹配邊：如果該邊的頭節(jié)點為間歇節(jié)點，尾節(jié)點為間歇節(jié)點，并且該邊參與部分最大匹配，則這個邊稱為間歇輸出不完全匹配和間歇輸入不完全匹配邊（Intermittent Output No Perfect Matching and Intermittent Input No Perfect Matching，簡稱IOOPM-IIOPM）。

類型9 冗余輸出不完全匹配和間歇輸入不完全匹配邊：如果該邊的頭節(jié)點為冗余節(jié)點，尾節(jié)點為間歇節(jié)點，并且該邊參與部分最大匹配，則這個邊稱為冗余輸出不完全匹配和間歇輸入不完全匹配邊（Redundant Output No Perfect Matching and Intermittent Input No Perfect Matching，簡稱ROOPM-IIOPM）。

類型10 關(guān)鍵輸出不匹配和冗余輸入不匹配邊：如果該邊的頭節(jié)點為關(guān)鍵節(jié)點，尾節(jié)點為冗余節(jié)點，并且該邊不參與任意一個最大匹配，則這個邊稱為關(guān)鍵輸出不匹配和冗余不完全匹配邊（Critical Output No Matching and Redundant Input No Matching，簡稱COOM-RIOM）。

類型11 間歇輸出不匹配和冗余輸入不匹配邊：如果該邊的頭節(jié)點為間歇節(jié)點，尾節(jié)點為冗余節(jié)點，并且該邊不參與任意一個最大匹配，則這個邊稱為間歇輸出不匹配和冗余輸入不匹配邊（Intermittent Output No Matching and Redundant Input No Matching，簡稱IOOM-RIOM）。

類型12 冗余輸出不匹配和冗余輸入不匹配邊：如果該邊的頭節(jié)點為冗余節(jié)點，尾節(jié)點為冗余節(jié)點，并且該邊不參與任意一個最大匹配，則這個邊稱為冗余輸出不匹配和冗余輸入不匹配邊（Redundant Output No Matching and Redundant Input No Matching，簡稱ROOM-RIOM）。

對于圖2a和2b網(wǎng)絡(luò)，對應(yīng)二分網(wǎng)絡(luò)如圖3a和3b所示，根據(jù)邊分類可知，邊（1→2）參與全部最大匹配，且節(jié)點1為關(guān)鍵節(jié)點，節(jié)點2為冗余節(jié)點，所以邊（1→2）為COM-RIM邊。同理邊（1→3）為COOM-RIOM邊，邊（2→3）、（6→7）、（16→18）和（18→17）為ROM-RIM邊，邊（3→4）和（3→5）為ROOPM-IIOPM邊，邊（4→8）、（5→6）和（20→19）為IOM-RIM邊，邊（5→7）為IOOM-RIOM邊，邊（8→9）為ROOPM-RIOPM邊，邊（10→9）為COOPM-RIOPM邊，邊（11→12）和（11→20）為IOOPM-IIOPM邊，邊（13→11）和（13→14）為COOPM-IIOPM邊，邊（14→16）為IOOPM-RIOPM邊，邊（15→16）為COOPM-RIOPM邊，邊（16→17）為ROOM-RIOM邊。

2.2 邊辨識算法

為研究轉(zhuǎn)換邊和增加邊對網(wǎng)絡(luò)能控性的影響，需先對網(wǎng)絡(luò)邊類型進(jìn)行辨識。本節(jié)給出辨識網(wǎng)絡(luò)邊類型的算法，流程圖如圖4所示。具體步驟為：

步驟1：識別網(wǎng)絡(luò)的最大匹配邊數(shù)m和網(wǎng)絡(luò)總邊數(shù)L，并令參數(shù)a=0。

步驟2：將網(wǎng)絡(luò)節(jié)點編號，記為y1，y2，…yN（N為網(wǎng)絡(luò)節(jié)點數(shù)目）。選擇網(wǎng)絡(luò)中一條邊（yi→yj），去除該邊后，識別新網(wǎng)絡(luò)最大匹配邊數(shù)m1，判斷是否滿足m1=m-1，若不滿足，則跳至步驟3；否則跳至步驟4。

步驟3：去除節(jié)點yi的輸入邊和節(jié)點yj的輸出邊后，識別新網(wǎng)絡(luò)的最大匹配邊數(shù)m2，判斷是否滿足m2=m-1，若不滿足，則跳至步驟6；否則跳至步驟5。

步驟4：邊（yi→yj）為完全匹配邊。判斷節(jié)點yi是否存在輸入邊，若節(jié)點yi不存在輸入邊，則該邊為COM-RIM邊；若存在，則去掉節(jié)點yi的輸入邊，識別新網(wǎng)絡(luò)最大匹配邊數(shù)m3，若滿足m3=m-1，則該邊為ROM-RIM邊；否則為IOM-RIM邊。

步驟5：邊（yi→yj）為不匹配邊。判斷節(jié)點是否存在輸入邊，若節(jié)點yi不存在輸入邊，則該邊為COOM-RIOM邊；若存在，則去除節(jié)點yi的輸入邊，識別新網(wǎng)絡(luò)的最大匹配邊數(shù)m4，若滿足m4=m-1，則該邊為ROOM-RIOM邊；否則為IOOM-RIOM邊。

步驟6：邊（yi→yj）為不完全匹配邊。判斷節(jié)點yi是否存在輸入邊，若不存在輸入邊，則跳至步驟7；若存在輸入邊，則跳至步驟8。

步驟7：節(jié)點yi為關(guān)鍵節(jié)點，去除節(jié)點yj的輸入邊，識別新網(wǎng)絡(luò)的最大匹配邊數(shù)m5，若滿足m5=m-1，則節(jié)點yj為冗余節(jié)點，而邊（yi→yj）為COOPM-RIOPM邊；若不滿足m5=m-1，則節(jié)點為間歇節(jié)點，邊（yi→yj）為COOPM-IIOPM邊。

步驟8：去除節(jié)點yi的輸入邊，識別新網(wǎng)絡(luò)的最大匹配邊數(shù)m6，若滿足m6=m-1，則跳至步驟9；若不滿足m6=m-1，則跳至步驟10。

步驟9：節(jié)點yi為冗余節(jié)點，然后去除節(jié)點yj的輸入邊，并識別新網(wǎng)絡(luò)的最大匹配邊數(shù)m7，若滿足m7=m-1，則節(jié)點yj為冗余節(jié)點，邊（yi→yj）為ROOPM-RIOPM邊；若不滿足m7=m-1，則節(jié)點為間歇節(jié)點，而邊（yi→yj）為ROOPM-IIOPM邊。

步驟10：節(jié)點yi為間歇節(jié)點，然后去除節(jié)點yj的輸入邊，識別新網(wǎng)絡(luò)的最大匹配邊數(shù)m8，若滿足m8=m-1，則節(jié)點yj為冗余節(jié)點，邊（yi→yj）為IOOPM-RIOPM邊；若不滿足m8=m-1，則節(jié)點yj為間歇節(jié)點，邊（yi→yj）為IOOPM-IIOPM邊。

步驟11：若a＜L，則a=a+1，返回步驟2；否則結(jié)束操作。

3 轉(zhuǎn)換邊與增加邊對網(wǎng)絡(luò)能控性的影響

3.1 轉(zhuǎn)換邊對網(wǎng)絡(luò)能控性的影響

對于有向網(wǎng)絡(luò)，轉(zhuǎn)換不同的邊對網(wǎng)絡(luò)能控性有不同的影響?？紤]到轉(zhuǎn)換邊的現(xiàn)實意義，本節(jié)給出邊轉(zhuǎn)換使網(wǎng)絡(luò)驅(qū)動節(jié)點數(shù)目減少和不變的變化規(guī)律。

定理1 對于N個節(jié)點的有向網(wǎng)絡(luò)，轉(zhuǎn)換一條邊類型為COOM-RIOM、IOOM-RIOM、COOPM-RIOPM、IOOPM-RIOPM，如果該邊尾節(jié)點出度為0；或轉(zhuǎn)換一條邊類型為COOPM-IIOPM、IOOPM-IIOPM，如果該邊尾節(jié)點出度為0且入度為1，則網(wǎng)絡(luò)中的最大匹配數(shù)增加1，驅(qū)動節(jié)點數(shù)減少1。

證明：設(shè)網(wǎng)絡(luò)有N個節(jié)點，最大匹配邊為L，由二分圖得到最大匹配中被匹配的節(jié)點個數(shù)為M，最小驅(qū)動節(jié)點數(shù)目為ND=N-M，轉(zhuǎn)換邊后的最小驅(qū)動節(jié)點數(shù)目為ND′。對于COOPM-RIOPM邊或COOM-RIOM邊，原頭節(jié)點是關(guān)鍵節(jié)點，轉(zhuǎn)換邊后，被原尾節(jié)點匹配，變?yōu)槿哂喙?jié)點。原尾節(jié)點為冗余節(jié)點，轉(zhuǎn)換邊后，被其它節(jié)點匹配，故被匹配節(jié)點數(shù)目為M+1，驅(qū)動節(jié)點數(shù)目變?yōu)镹D′=N-（M+1）=N-M-1=ND-1，驅(qū)動節(jié)點數(shù)目減少1。對于IOOM-RIOM邊或IOOPM-RIOPM邊，原頭節(jié)點是間歇節(jié)點，轉(zhuǎn)換邊后，被原冗余節(jié)點匹配，變?yōu)槿哂喙?jié)點。原尾節(jié)點為冗余節(jié)點，轉(zhuǎn)換邊后，仍被其他節(jié)點匹配，故被匹配的節(jié)點數(shù)目為M+1，驅(qū)動節(jié)點數(shù)目變?yōu)镹D′=N-（M+1）=N-M-1=ND-1，驅(qū)動節(jié)點數(shù)目減少1。對于COOPM-IIOPM邊或IOOPM-IIOPM邊，原頭節(jié)點為關(guān)鍵節(jié)點或間歇節(jié)點，轉(zhuǎn)換邊后，被原尾節(jié)點匹配，變?yōu)槿哂喙?jié)點。原尾節(jié)點為間歇節(jié)點且出度為0，轉(zhuǎn)換邊后，變?yōu)殛P(guān)鍵節(jié)點，而同頭節(jié)點下的其他間歇節(jié)點必會有一個被匹配，故被匹配節(jié)點數(shù)目為M+1，驅(qū)動節(jié)點數(shù)目為ND′=N-（M+1）=N-M-1=ND-1，驅(qū)動節(jié)點數(shù)目減少1。

定理2 對于N個節(jié)點有向網(wǎng)絡(luò)，轉(zhuǎn)換一條邊類型為COM-RIM、ROOM-RIOM、ROOPM-RIOPM、IOM-RIM，如果該邊尾節(jié)點出度為0；或轉(zhuǎn)換一條ROOPM-IIOPM邊，如果該邊尾節(jié)點出度為0且入度為1；或轉(zhuǎn)換一條ROM-RIM邊，如果該邊尾節(jié)點出度為0且入度為2，則網(wǎng)絡(luò)中最大匹配數(shù)不增加，驅(qū)動節(jié)點數(shù)也不改變。

證明：設(shè)網(wǎng)絡(luò)有N個節(jié)點，最大匹配邊為L，由二分圖得到最大匹配中被匹配的節(jié)點個數(shù)為M，驅(qū)動節(jié)點個數(shù)為ND=N-M，轉(zhuǎn)換邊后的最小驅(qū)動節(jié)點數(shù)目為ND′。對于ROM-RIM邊、ROOM-RIOM邊或ROOPM-RIOPM邊，原頭節(jié)點為冗余節(jié)點，轉(zhuǎn)換邊后，被原尾節(jié)點匹配。原尾節(jié)點為冗余節(jié)點，存在其他節(jié)點匹配該尾節(jié)點，轉(zhuǎn)換邊后，仍被其他節(jié)點匹配，故網(wǎng)絡(luò)中被匹配節(jié)點數(shù)目為M，驅(qū)動節(jié)點數(shù)目為ND′=N-M=ND，驅(qū)動節(jié)點的數(shù)目不變。對于COM-RIM邊、IOM-RIM邊或ROOPM-IIOPM邊，原頭節(jié)點為關(guān)鍵節(jié)點、間歇節(jié)點或冗余節(jié)點，轉(zhuǎn)換邊后，被原尾節(jié)點匹配。原尾節(jié)點為間歇節(jié)點或冗余節(jié)點且出度為0，轉(zhuǎn)換邊后，不被匹配，變?yōu)殛P(guān)鍵節(jié)點，故網(wǎng)絡(luò)中被匹配節(jié)點數(shù)目為M，驅(qū)動節(jié)點數(shù)目為ND′=N-M=ND，驅(qū)動節(jié)點數(shù)目保持不變。

3.2 增加邊對網(wǎng)絡(luò)能控性的影響

對于有向網(wǎng)絡(luò)，在不同節(jié)點間增加邊對網(wǎng)絡(luò)能控性有不同的影響?？紤]到增加邊的現(xiàn)實意義，本節(jié)將給出增加邊使網(wǎng)絡(luò)驅(qū)動節(jié)點數(shù)目減少的變化規(guī)律。

定理3 對于N個節(jié)點的有向網(wǎng)絡(luò)，考慮以下情況時，網(wǎng)絡(luò)最大匹配數(shù)增加1，驅(qū)動節(jié)點數(shù)減少1。1）在COOPM-IIOPM邊、IOOPM-IIOPM邊、ROOPM-IIOPM邊的尾節(jié)點之間增加一條邊l1，如果l1的頭節(jié)點出度為1；2）在COOPM-RIOPM邊、IOOPM-RIOPM邊的頭節(jié)點與COOPM-RIOPM邊、IOOPM-RIOPM邊、ROOPM-RIOPM邊的頭節(jié)點之間增加一條邊l2，如果l2的尾節(jié)點為關(guān)鍵節(jié)點或間歇節(jié)點；3）在出度為0的邊尾節(jié)點與邊類型為COM-RIM、COOM-RIOM、COOPM-IIOPM或COOPM-RIOPM的頭節(jié)點間增加一條邊l3。