引言

多處理器系統(tǒng)的應(yīng)用領(lǐng)域廣泛，成為解決科學(xué)與工程計算領(lǐng)域的必備工具，但多處理器系統(tǒng)由于物理磨損、電磁干擾以及自身壽命等原因容易發(fā)生故障，故多處理器系統(tǒng)在設(shè)計或者選擇超立方體網(wǎng)絡(luò)時，必須考慮超立方體網(wǎng)絡(luò)的容錯性[1-2]，否則會影響多處理器系統(tǒng)的正常運(yùn)作。 （n，k）. 星圖網(wǎng)絡(luò)[3作為超立方體網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的一個很好替代，有更小的點(diǎn)度、更短的直徑以及更高的容錯性，同時還保留了點(diǎn)邊對稱，層次結(jié)構(gòu)等星圖的性質(zhì)。PMC（Pairwise MultipleComparison）模型[4]作為經(jīng)典的系統(tǒng)級故障診斷模型，可以診斷多處理器系統(tǒng)的故障，故可使用PMC模型對 （n，k）. -星圖網(wǎng)絡(luò)進(jìn)行故障診斷，進(jìn)而確定 （n，k）. 星圖網(wǎng)絡(luò)中故障點(diǎn)個數(shù)。

針對 -星圖網(wǎng)絡(luò)（簡稱 （n，k） 網(wǎng)絡(luò)）容錯性問題，采用改進(jìn)自適應(yīng)順序診斷算法、深度優(yōu)先遍歷算法、枚舉法等5，解決如下3個問題：

（1）在（6，4）網(wǎng)絡(luò)中，設(shè)定故障頂點(diǎn)的個數(shù)不會超過5個，根據(jù)（6，4）網(wǎng)絡(luò)一次自診斷產(chǎn)生的報告，求解出（6，4）網(wǎng)絡(luò)中的所有故障點(diǎn)個數(shù)以及所有故障點(diǎn)個數(shù)的具體位置；

（2）將（6，4）網(wǎng)絡(luò)擴(kuò)展到 （n，k） 網(wǎng)絡(luò)中，即在 （n，k） 網(wǎng)絡(luò)中設(shè)定一個點(diǎn)周圍不全是故障點(diǎn)，根據(jù) （n，k） 網(wǎng)絡(luò)以此自診斷產(chǎn)生的報告，需求出 （n，k） 網(wǎng)絡(luò)中的所有故障點(diǎn)個數(shù);

（3）若 （n，k） 網(wǎng)絡(luò)所包含的所有子網(wǎng)絡(luò)都被破壞，則 （n，k） 網(wǎng)絡(luò)一些功能不能實(shí)現(xiàn)。（6，4）網(wǎng)絡(luò)中包含多少個不同的（4，2）子網(wǎng)絡(luò)，如果要破壞（6，4）網(wǎng)絡(luò)中的所有（4，2）子網(wǎng)絡(luò)，那么至少要破壞幾個頂點(diǎn)，且如何破壞。

1確定（6，4）網(wǎng)絡(luò)故障點(diǎn)個數(shù)及具體位置

1.1 （6，4）網(wǎng)絡(luò)故障點(diǎn)個數(shù)的數(shù)據(jù)預(yù)處理

針對（6，4）網(wǎng)絡(luò)自診斷產(chǎn)生報告中提供的 3600×3600 組數(shù)據(jù)，即（6，4）網(wǎng)絡(luò)自診斷產(chǎn)生報告數(shù)據(jù)表，如表1所示，進(jìn)行數(shù)據(jù)預(yù)處理]

在表1中，遍歷（6，4）網(wǎng)絡(luò)自診斷產(chǎn)生報告中的每一個點(diǎn)，提取出（6，4）網(wǎng)絡(luò)自診斷產(chǎn)生報告中37組\"-1\"對應(yīng)的故障點(diǎn)數(shù)據(jù)，構(gòu)成（6，4）網(wǎng)絡(luò)故障可疑點(diǎn)集合；同時提?。?，4）網(wǎng)絡(luò)自診斷產(chǎn)報告中，“1\"對應(yīng)的數(shù)據(jù)為無故障點(diǎn)數(shù)據(jù)，構(gòu)成（6，4）網(wǎng)絡(luò)無故障點(diǎn)集合。（6，4）網(wǎng)絡(luò)37組數(shù)據(jù)故障可疑點(diǎn)提取圖，如圖1所示。

1.2（6，4）網(wǎng)絡(luò)故障點(diǎn)個數(shù)的PMC模型建立

PMC模型的工作原理為：當(dāng)測試者處于無故障狀態(tài)時，可以準(zhǔn)確判斷被測試者的狀態(tài)，說明無故障測試者所測試的結(jié)果是可靠的；當(dāng)測試者處于故障狀態(tài)時，被測試者狀態(tài)的結(jié)果是隨機(jī)出現(xiàn)的，說明故障測試者所測試的結(jié)果不可靠。

在（6，4）網(wǎng)絡(luò)自診斷產(chǎn)生的報告中， R（U，V） 表示一個點(diǎn) U 報告另外一個點(diǎn) V ，即 U 表示（6，4）網(wǎng)絡(luò)自診斷產(chǎn)生的報告中一行中的一個點(diǎn)，V表示（6，4）網(wǎng)絡(luò)自診斷產(chǎn)生的報告中一列中的一個點(diǎn)。若一個本身無故障 U 報告另外一個點(diǎn) V 無故障，則R（U，V）=1 ;若一個點(diǎn) U 為故障，報告另外一個點(diǎn) V可能為無故障或者有故障，則所得測試結(jié)果不可靠，且 R（U，V）=-1 。

由PMC模型結(jié)論可知：若 R（U，V）=1 ，則 U，V 中至少一個是故障的;若 R（U，V）=0^[7] ，則 U，V 均是無故障的。

總之，若 ，則 U，V 中至少一個是無故障的；若 R（U，V）=1 ，則 U，V 均是無故障的。（6，4）網(wǎng)絡(luò)故障點(diǎn)個數(shù)的PMC模型，如表2所示。

1.3基于改進(jìn)自適應(yīng)順序診斷算法對（6，4）網(wǎng)絡(luò)故障點(diǎn)個數(shù)的PMC模型求解

改進(jìn)自適應(yīng)順序診斷算法[8]，需先準(zhǔn)備一個可以輪回的測試，即（6，4）網(wǎng)絡(luò)自診斷產(chǎn)生報告的每一列相加得到的數(shù)據(jù)集合。從數(shù)據(jù)集合中選擇節(jié)點(diǎn)進(jìn)行測試，進(jìn)而診斷出部分節(jié)點(diǎn)的故障狀態(tài)，在上一個診斷結(jié)果的基礎(chǔ)之上進(jìn)行下一次的輪回測試，直到所有數(shù)據(jù)集合中節(jié)點(diǎn)的故障狀態(tài)可以確定。

由于（6，4）網(wǎng)絡(luò)37組數(shù)據(jù)故障可疑點(diǎn)中，必有故障頂點(diǎn)的個數(shù)不會超過5個，故采用改進(jìn)自適應(yīng)順序診斷算法，對（6，4）網(wǎng)絡(luò)故障點(diǎn)9個數(shù)的PMC模型進(jìn)行求解，有如下4個具體步驟：

第1步：將（6，4）網(wǎng)絡(luò)自診斷產(chǎn)生報告中每一個被檢測值的結(jié)果相加（即為（6，4）網(wǎng)絡(luò)自診斷產(chǎn)生報告的每一列相加），故得出數(shù)據(jù)集合。

第2步：在（6，4）網(wǎng)絡(luò)自診斷產(chǎn)生報告中，行為測試點(diǎn)的報告，列為被檢測點(diǎn)的報告。當(dāng)被檢測值為全連

通無故障的被檢測點(diǎn)（即一個點(diǎn)周圍均為無故障）時，將其組成一個單獨(dú)的集合?？梢暬B通無故障的被檢測點(diǎn)，如圖2所示。

第3步：數(shù)據(jù)集合中第一個點(diǎn)開始對（6，4）網(wǎng)絡(luò)自診斷產(chǎn)生的報告進(jìn)行輪回測試，進(jìn)而診斷出節(jié)點(diǎn)的故障狀態(tài)。若得到值為-1的點(diǎn)，則需記錄此點(diǎn)，直至整個輪回結(jié)束。

第4步：開始選擇數(shù)據(jù)集合中的第二個集合點(diǎn)，繼續(xù)進(jìn)行輪回，直到輪回結(jié)束為止，以此類推，直至數(shù)據(jù)集合中的所有點(diǎn)均進(jìn)行輪回測試。

改進(jìn)自適應(yīng)順序診斷算法通過引入動態(tài)調(diào)整機(jī)制、自適應(yīng)策略和減少通信開銷，在診斷精度、時間和系

統(tǒng)負(fù)載方面優(yōu)于無改進(jìn)的自適應(yīng)順序診斷算法。若采用改進(jìn)自適應(yīng)順序診斷算法在360×360 組數(shù)據(jù)中尋找故障點(diǎn)，則故障點(diǎn)尋找時間為1.052002秒；若采用未改進(jìn)自適應(yīng)診斷算法在 360×360 組數(shù)據(jù)中尋找故障點(diǎn)，則故障點(diǎn)尋找時間為2.105742秒，故可知采用改進(jìn)自適應(yīng)順序診斷算法尋找故障點(diǎn)為較優(yōu)算法。

1.4（6，4）網(wǎng)絡(luò)故障點(diǎn)個數(shù)的PMC模型求解結(jié)果

采用改進(jìn)自適應(yīng)順序診斷算法，從（6，4）網(wǎng)絡(luò)37組數(shù)據(jù)故障可疑點(diǎn)中，對（6，4）網(wǎng)絡(luò)故障點(diǎn)的PMC模型求解的結(jié)果為：（6，4）網(wǎng)絡(luò)中所有故障點(diǎn)共有5個，分別為1426、3416、4216、5416和6412?？梢暬?，4）網(wǎng)絡(luò)中5個故障點(diǎn)，如圖3所示。

1.5 （6，4）網(wǎng)絡(luò)故障點(diǎn)的具體位置

通過對（6，4）網(wǎng)絡(luò)故障點(diǎn)個數(shù)求解，可知（6，4）網(wǎng)絡(luò)故障點(diǎn)有5個，分別為：1426、3416、4216、5416和6412，采用深度優(yōu)先遍歷算法[10]，根據(jù)（6，4）網(wǎng)絡(luò)鄰接矩陣創(chuàng)建（6，4）網(wǎng)絡(luò)無向圖，其中（6，4）網(wǎng)絡(luò)中5個故障點(diǎn)為紅色，其余點(diǎn)為白色。（6，4）網(wǎng)絡(luò)故障點(diǎn)位置圖，如圖4所示。

總之，針對求解（6，4）網(wǎng)絡(luò)故障點(diǎn)個數(shù)的問題，首先，對（6，4）網(wǎng)絡(luò)自診斷產(chǎn)生的報告進(jìn)行數(shù)據(jù)預(yù)處理，篩選出37組\"-1\"對應(yīng)的故障可疑點(diǎn)數(shù)據(jù)，可知在37組報錯數(shù)據(jù)中至多有5個故障點(diǎn)。其次，構(gòu)建（6，4）網(wǎng)絡(luò)故障點(diǎn)的PMC模型，采用改進(jìn)自適應(yīng)順序診斷算法對（6，4）網(wǎng)絡(luò)故障點(diǎn)的PMC模型進(jìn)行求解。最后，計算得出（6，4）網(wǎng)絡(luò)中所有故障點(diǎn)共有5個，分別為1426、3416、4216、5416和6412，并標(biāo)識出（6，4）網(wǎng)絡(luò)中這5個故障點(diǎn)的具體位置。

2 確定 （n，k） 網(wǎng)絡(luò)所有故障點(diǎn)個數(shù)

2.1數(shù)據(jù)預(yù)處理及 （n，k） 網(wǎng)絡(luò)故障點(diǎn)個數(shù)PMC模型的建立

對于 （n，k） 網(wǎng)絡(luò)自診斷產(chǎn)生報告中的數(shù)據(jù)進(jìn)行預(yù)處理，提取 （n，k） 網(wǎng)絡(luò)自診斷產(chǎn)生報告中“-1\"對應(yīng)的故障點(diǎn)數(shù)據(jù)集合，同時提取 （n，k） 網(wǎng)絡(luò)自診斷產(chǎn)生的報告中“1\"對應(yīng)的數(shù)據(jù)，即無故障點(diǎn)數(shù)據(jù)。

在 （n，k） 網(wǎng)絡(luò)自診斷產(chǎn)生的報告中，一行中的點(diǎn)報告一列中的點(diǎn)，即 U 報告 V_? 。如果兩個點(diǎn)不相鄰，那么R（U，V）=0 ；如果一個點(diǎn) U 本身無故障報告另外一個點(diǎn)V無故障時，那么 R（U，V）=1 ;如果一個點(diǎn) U 為故障，報告另外一個點(diǎn)V可能為無故障或者有故障時，那么所得測試結(jié)果不可靠，即 。

（n，k） 網(wǎng)絡(luò)故障點(diǎn)個數(shù)的PMC模型為：若 R（U，V）=0 ，則 U，V 兩點(diǎn)不相鄰；若 R（U，V）=-1 ，則U，V中至少一個是無故障的;若 R（U，V）=1 ，則 U，V 均是無故障的。

2.2基于改進(jìn)自適應(yīng)順序診斷算法對 （n，k） 網(wǎng)絡(luò)故障點(diǎn)個數(shù)的求解

根據(jù)改進(jìn)自適應(yīng)診斷算法求解（6，4）網(wǎng)絡(luò)故障點(diǎn)個數(shù)的思路，將改進(jìn)自適應(yīng)診斷算法推廣到 （n，k） 網(wǎng)絡(luò)中。首先，在 （n，k） 網(wǎng)絡(luò)自診斷產(chǎn)生報告中，將每一列相加得到數(shù)據(jù)集合，在該數(shù)據(jù)集合中進(jìn)行一個輪回測試；再在 （n，k） 網(wǎng)絡(luò)數(shù)據(jù)集合中選取節(jié)點(diǎn)進(jìn)行測試，進(jìn)而診斷出部分節(jié)點(diǎn)的故障狀態(tài);然后在上一個診斷結(jié)果的基礎(chǔ)上進(jìn)行下一次的輪回測試，直到所有數(shù)據(jù)集合中節(jié)點(diǎn)的故障狀態(tài)可以確定。采用改進(jìn)自適應(yīng)診斷算法，對 （n，k） 網(wǎng)絡(luò)故障點(diǎn)個數(shù)求解的具體步驟為：

第1步：將 （n，k） 網(wǎng)絡(luò)自診斷產(chǎn)生報告中每一個被檢測值的結(jié)果相加，得出數(shù)據(jù)集合。第2步：在 （n，k） 網(wǎng)絡(luò)自診斷產(chǎn)生報告中，在被檢測值為全連通無故障的被檢測點(diǎn)，將全連通無故障被檢測點(diǎn)組成一個單獨(dú)的集合。

第3步：從數(shù)據(jù)集合中的第一個點(diǎn)開始對 （n，k） 網(wǎng)絡(luò)自診斷產(chǎn)生的報告進(jìn)行輪回測試，進(jìn)而診斷節(jié)點(diǎn)的故障狀態(tài)。如果得到值為-1的點(diǎn)，那么需要記錄此點(diǎn)，直到整個輪回結(jié)束。

第4步：選擇數(shù)據(jù)集合中的第二個集合點(diǎn)，繼續(xù)進(jìn)行輪回，直到數(shù)據(jù)集合中的所有點(diǎn)均進(jìn)行輪回測試為止，最終得出 （n，k） 網(wǎng)絡(luò)故障點(diǎn)個數(shù)。

2.3確定 （n，k） 網(wǎng)絡(luò)故障點(diǎn)個數(shù)的實(shí)例分析

在 （n，k） 網(wǎng)絡(luò)中，以（7，4）網(wǎng)絡(luò)實(shí)例，采用改進(jìn)自適應(yīng)順序診斷算法，對（7，4）網(wǎng)絡(luò)故障點(diǎn)個數(shù)進(jìn)行求解。

首先，需要對（7，4）網(wǎng)絡(luò)自診斷產(chǎn)生的報告進(jìn)行數(shù)據(jù)預(yù)處理，實(shí)現(xiàn)數(shù)據(jù)篩選，從而得到112組故障點(diǎn)數(shù)據(jù)。若一個點(diǎn)周圍六個點(diǎn)均為故障，則無法判斷中間點(diǎn)是否為故障點(diǎn);若一個點(diǎn)周圍六個點(diǎn)不全為故障點(diǎn)，則可以判斷中間點(diǎn)是否為故障點(diǎn)。其次，構(gòu)建（7，4）網(wǎng)絡(luò)故障點(diǎn)的PMC模型，采用改進(jìn)自適應(yīng)診斷算法，得出全連通無故障的被檢測點(diǎn)的數(shù)據(jù)集合。從集合中的第一個點(diǎn)開始，若得到-1，則需記錄此點(diǎn)，直至整個輪回結(jié)束，周而復(fù)始，直到數(shù)據(jù)集合中的所有點(diǎn)均進(jìn)行輪回為止。最后，計算得出（7，4）網(wǎng)絡(luò)中所有故障點(diǎn)共有12個，分別為2465、2643、2763、3741、4523、4527、4756、5162、5716、6153和7653。

3確定（6，4）網(wǎng)絡(luò)中（4，2）子網(wǎng)絡(luò)個數(shù)及破壞頂點(diǎn)個數(shù)

3.1確定（6，4）網(wǎng)絡(luò)中（4，2）子網(wǎng)絡(luò)個數(shù)

馮凱提出子網(wǎng)絡(luò)組合排列理論： S_n，k 中共有 個不同的 S_{n-m，k-m} 子網(wǎng)絡(luò)，且任意一個S_n-m，k-m 子網(wǎng)絡(luò)可用某個 唯一表示，其中 1?m?k-1 。

根據(jù)上述理論，設(shè) S_n，k 為 （n，k） 網(wǎng)絡(luò)， S_{n-m，k-m} 為子網(wǎng)絡(luò)，那么（6，4）網(wǎng)絡(luò)為 S_6，4，（4，2） 子網(wǎng)絡(luò)為 S_4，2 ，由 與 n ！相乘，再用乘積除以 （n-m）！ ，得出公式：

為確定（6，4）網(wǎng)絡(luò)中（4，2）子網(wǎng)絡(luò)個數(shù)，故令 n=6，k=4，m=2 ，代入公式（1）為：

進(jìn)而由公式（2）得出：（6，4）網(wǎng)絡(luò)含有90個不同的（4，2）子網(wǎng)絡(luò)。

可視化（6，4）網(wǎng)絡(luò)中90個不同的（4，2）子網(wǎng)絡(luò)及頂點(diǎn)[1]，如圖5所示。

3.2確定破壞（6，4）網(wǎng)絡(luò)中（4，2）子網(wǎng)絡(luò)的頂點(diǎn)個數(shù)

為破壞（6，4）網(wǎng)絡(luò)中的所有（4，2）子網(wǎng)絡(luò)[12]，需求解出至少破壞頂點(diǎn)個數(shù)，進(jìn)而制定出對應(yīng)的（4，2）子網(wǎng)絡(luò)破壞策略。在（6，4）網(wǎng)絡(luò)中擁有90個不同的（4，2）子網(wǎng)絡(luò)，但在（6，4）網(wǎng)絡(luò)頂點(diǎn)中出現(xiàn)將所有（4，2）子網(wǎng)絡(luò)

中的點(diǎn)覆蓋，而不會有單獨(dú)一個點(diǎn)未被覆蓋的情況可視化（6，4）網(wǎng)絡(luò)的（4，2）子網(wǎng)絡(luò)覆蓋，如圖6所示。

3.2.1基于枚舉法求解破壞（6，4）網(wǎng)絡(luò)中（4，2）子網(wǎng)絡(luò)的頂點(diǎn)個數(shù)

通過枚舉法，列舉在（6，4）網(wǎng)絡(luò)中所有四位不相同數(shù)字組合的所有可能，將所有狀態(tài)逐一與目標(biāo)狀態(tài)進(jìn)行比較，從而得到滿足所有組合的特定位置數(shù)據(jù)與固定點(diǎn)數(shù)據(jù)相同組合的解。

采用枚舉法，對（6，4）網(wǎng)絡(luò)需要破壞（4，2）子網(wǎng)絡(luò)頂點(diǎn)個數(shù)進(jìn)行求解，有如下4個步驟：

第1步：通過嵌套[13]生成4位不相同數(shù)字可能的所有組合，將4位不相同的數(shù)字組合成矩陣，故可以把由4位不同數(shù)字組合成的矩陣作為（6，4）網(wǎng)絡(luò)的頂點(diǎn)編號。

第2步：需要經(jīng)過嵌套迭代尋找固定點(diǎn)的組合，并從生成的所有組合中，篩選出滿足特定條件（即所有組

合的特定位置數(shù)據(jù)與固定點(diǎn)數(shù)據(jù)相同）的組合。在滿足放到一個臨時存儲空間的前提下，需要尋找所有可能的組合，與此同時，需要觀察臨時存儲空間中的數(shù)據(jù)是否為一個子圖的數(shù)據(jù)。若臨時存儲空間中的數(shù)據(jù)為一個子圖的數(shù)據(jù)，則需要把滿足特定條件的所有組合放到總存儲列表中，否則需要把臨時存儲空間記為空。

第3步：通過統(tǒng)計在總列表（所有子網(wǎng)絡(luò)形成）中每個組合（即（6，4）網(wǎng)絡(luò)中每個頂點(diǎn)）出現(xiàn)的次數(shù)，并將每個組合按照降序排列形成一個新的集合。

第4步：去除集合中按降序[14]排列的第一個組合，將集合中剩余組合返回到第二步當(dāng)中，繼續(xù)進(jìn)行迭代。以此類推，直到?jīng)]有（4，2）子網(wǎng)絡(luò)結(jié)束為止。

隨破壞頂點(diǎn)個數(shù)，（6.4）網(wǎng)絡(luò)中所有子網(wǎng)絡(luò)所包含的頂點(diǎn)個數(shù)變化圖，如圖7所示。

3.2.2破壞（6，4）網(wǎng)絡(luò)中（4，2）子網(wǎng)絡(luò)的頂點(diǎn)個數(shù)結(jié)果

運(yùn)用枚舉法對（6，4）網(wǎng)絡(luò)破壞（4，2）子網(wǎng)絡(luò)頂點(diǎn)個數(shù)的求解結(jié)果為：破壞（6.4）網(wǎng)絡(luò)中的所有（4，2）子網(wǎng)絡(luò)，至少需要破壞42個頂點(diǎn)，分別為1234、1243、1256、1265、1324、1342、1423、1432、1526、1562、1625、1652、2135、2146、2153、2164、2315、2351、2416、2461、2513、2531、2614、2641、1236、1245、1254、1263、1326、1362、1425、1452、1524、1542、1623、1632、3124、3142、3214、3241、3412和3421。

可視化（6，4）網(wǎng)絡(luò)破壞（4，2）子網(wǎng)絡(luò)42個頂點(diǎn)，如圖8所示。3.2.3（6，4）網(wǎng)絡(luò)破壞（4，2）子網(wǎng)絡(luò)頂點(diǎn)個數(shù)的結(jié)果檢驗(yàn)

馮凱提出： 為在 S_n，k 中使每個 S_n-m，k-m 變得有故障的最小故障頂點(diǎn)數(shù)（在系統(tǒng)的頂點(diǎn)故障模型下）[15]，其中 1?k?n-2 和 2?j?k-2 ，即：

對（6，4）網(wǎng)絡(luò)破壞（4，2）子網(wǎng)絡(luò)頂點(diǎn)個數(shù)中，在滿足 1?k?n-2 和 2?j?k-2 的前提下，令 n=6，k=4 j=2 ，代人公式（3）為：

由（4）式計算可得，（6，4）網(wǎng)絡(luò)破壞（4，2）子網(wǎng)絡(luò)頂點(diǎn)個數(shù)范圍為 30～48 。

破壞（6，4）網(wǎng)絡(luò)中的所有（4，2）子網(wǎng)絡(luò)，實(shí)際求解出至少需要破壞42個頂點(diǎn)，屬于（6，4）網(wǎng)絡(luò)破壞（4，2）子網(wǎng)絡(luò)頂點(diǎn)個數(shù) 30～48 范圍之內(nèi)，故檢驗(yàn)出破壞（6，4）網(wǎng)絡(luò)中的所有（4，2）子網(wǎng)絡(luò)，至少需要破壞42個頂點(diǎn)的可靠性高。

總之，為破壞（6，4）網(wǎng)絡(luò)中的所有（4，2）子網(wǎng)絡(luò)，求解出至少需要破壞42個頂點(diǎn)，制定出對應(yīng)的（4，2）子網(wǎng)絡(luò)破壞策略為：按照降序排列進(jìn)行新集合的生成過程中，將影響較大的頂點(diǎn)放在首位，即從影響子網(wǎng)絡(luò)最大的頂點(diǎn)開始破壞，一直破壞到42個頂點(diǎn)為止。

4結(jié)論

多處理器系統(tǒng)在設(shè)計或選擇 （n，k） 網(wǎng)絡(luò)時，須考慮 （n，k） 網(wǎng)絡(luò)的容錯。通過構(gòu)建（6，4）網(wǎng)絡(luò)和 （n，k） 網(wǎng)絡(luò)故障診斷PMC模型，用于診斷多處理器系統(tǒng)的故障，采用改進(jìn)自適應(yīng)診斷算法、深度優(yōu)先遍歷算法和枚舉法，確定（6，4）網(wǎng)絡(luò)和 （n，k） 網(wǎng)絡(luò)中故障點(diǎn)個數(shù)和故障點(diǎn)的具體位置，以及（6，4）網(wǎng)絡(luò)破壞（4，2）子網(wǎng)絡(luò)的頂點(diǎn)個數(shù)。由于 （n，k） 網(wǎng)絡(luò)故障點(diǎn)PMC模型具有高效性和可靠性高的特點(diǎn)，可快速求得 （n，k） 網(wǎng)絡(luò)故障點(diǎn)個數(shù)，故可將 （n，k） 網(wǎng)絡(luò)故障點(diǎn)PMC模型的應(yīng)用推廣到人工智能、科學(xué)與工程計算領(lǐng)域等方面。

參考文獻(xiàn)：

[1]李麗娜，原軍.具有缺弧和失效點(diǎn)的單定向超立方體的診斷度[J].太原科技大學(xué)學(xué)報，2024，4（3）：1-2

[2]范詩悅.鐵路通信網(wǎng)絡(luò)的可靠性與容錯性分析[J].電子技術(shù)，2024，53（2）：1-2.

[3]王世英，王琛.泡型星圖網(wǎng)絡(luò)的3限制診斷度（英文）[J].廣州大學(xué)學(xué)報（自然科學(xué)版），2021，20（1）：4-6.

[4]方思越，劉清.政策文獻(xiàn)量化研究中的PMC指數(shù)模型應(yīng)用述評[J].現(xiàn)代情報，2024，44（4）：2-3.

[5]李吉俊，董自健.基于最近鄰值和枚舉法的車號字符分割及拼接方法[J].江蘇海洋大學(xué)學(xué)報（自然科學(xué)版），2022，31（1）：5-9.

[6]徐敏，王平.基于深度LSTM殘差網(wǎng)絡(luò)的旋轉(zhuǎn)機(jī)械故障診斷研究[J].機(jī)床與液壓，2023，51（4）：2-4.

[7]馮凱，馬鑫玉 .（n，k）. 冒泡排序網(wǎng)絡(luò)的子網(wǎng)絡(luò)可靠性[J].計算機(jī)科學(xué)，2021，48（4）：1-4.

[8]張梓心，曾慧，吳軍剛，等.基于輪回選擇的玉米自交系J1644雜交種選育及配合力分析[J/OL].分子植物育種，1[2024-06-04]htp：/kns.

cnki.net/kcms/detail/46.1068.s.20221219.1327.006.html：10-11.

[9]肖瑤，郭帥，楊震，等.序列式低軌星座全連通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)設(shè)計方法[J].航空學(xué)報，2023，44（24）：4-11.

[10]馬新宇.基于深度優(yōu)先的鐵路站場圖遍歷算法研究[J].價值工程，2023，42（6）：1-2.

[11]劉泳杏，楊風(fēng)，柏慧，等.基于CiteSpace互聯(lián)網(wǎng)醫(yī)院研究進(jìn)展與趨勢可視化分析[J].醫(yī)學(xué)信息，2024，37（10）：2-3.

[12]楊騰，寧芊，陳炳才.基于小波變換和殘差神經(jīng)網(wǎng)絡(luò)模型的軸承故障診斷[J].現(xiàn)代計算機(jī)，2021（15）：2-4.

[13]田小潤，李晶，張建秀.含故障邊的k元4立方體中的哈密爾頓性[J].太原科技大學(xué)學(xué)報，2022，43（4）：1-5.

[14]張傳軍，趙海清.半群PC_n的極大冪等元生成子半群[J].山東大學(xué)學(xué)報（理學(xué)版），2021，56（12）：2-3.

[15]陳錢，陳康康，董興建，等.一種面向機(jī)械設(shè)備故障診斷的可解釋卷積神經(jīng)網(wǎng)絡(luò)[J/OL].機(jī)械工程學(xué)報，1[2024-07-18].htp：/kns.cnki.net/kc-ms/detail/11.2187.TH.20240204.1632.012.html：2-5

Research on （6，4） Network Fault Points and Destructive （4，2） Subnetworks

XIE Hui'，ZHANG Jian-guo2，KANG Xin-shu'，LI Xin2，BAI Jing-qi3 （1.Departai;t sity，Jinzhong9tiolodtoUityo

Abstract： Aiming at the problem of the number of fault points in the （n，k） network， the PMC model of the fault points in the （6，4） network and （n，k） network is established，and the number of fault points in the （6，4） network and （n，k） network is obtained by using the improved adaptive sequential diagnosis algorithm，and the specific location of the fault points in the ^{（6，4）} network is identified by the depth-first traversal algorithm. The number of （4，2） subnetworks in （6，4） networks is calculated according to the combination and arrangement theory of subnetworks. Enumeration method is used to obtain the vertices of the （4，2） subnetwork in the（6，4）network，and verify the reliability of the Vertices of the （4，2） subnetwork，and then develop the strategy of destroying the（4，2） subnetwork in the（6，4） network.

Keywords： （n，k） network；improved adaptive sequential diagnosis algorithm； depth-first traversal algorithm; enumeration method

（責(zé)任編輯：馬乃玉）