【摘要】：在現(xiàn)實生活中,對于給定的一個互連網(wǎng)絡(luò),如何定位一個故障是一個廣泛研究的問題,我們的想法是盡量利用較少的檢測量去精確定位故障. 我們將遇到的這類問題轉(zhuǎn)化成圖論問題,進而研究與測試集十分相似的參數(shù)——路徑分離數(shù).圖G的路徑分離集是路的集合P={P1,...,Pt},其中P1,...,Pt(?)G,對任意一對邊e,f∈E(G),存在Pi,Pj∈P,i≠j,使得e∈E(Pi),e(?)E(Pj)并且f(?)E(Pi),f∈E(Pj)圖G的路徑分離數(shù)(記為psn(G))是分離集中擁有的最小路徑個數(shù)(記|P|).psn(G)=min {|P|:P是圖G的路徑分離集} 本篇文章主要研究了一些圖類的路徑分離數(shù)問題.在猜想psn(G)=O(n)的基礎(chǔ)上,根據(jù)目前已有的方法、結(jié)論以及新的方法對一些特殊圖類(如Halin圖,輪圖,網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖)的路徑分離數(shù)進行研究. 本文主要的結(jié)果如下： (1)對n≥3階的圈Cn,有psn(Cn)=n； (2)對Halin圖Hn,有psn(Hn)≤k+2； (3)對輪圖Wn(n≥5),有psn(Wn)=n； (4)對benes網(wǎng)BB(n),有 (5)對網(wǎng)狀網(wǎng)G(l,m)l,m≥3,有
[Abstract]:In real life, for a given interconnection network, how to locate a fault is a widely studied problem. Our idea is to use as few measurements as possible to locate the fault accurately. This kind of problem is transformed into graph theory problem, and then the path separation number, which is very similar to the test set, is studied. The path separation set of graph G is the set of paths P = {P 1,., Pt}, where P 1,., Pt (?) G, for any pair of edges e, f? e (G), has Pi, Pj? P, I 鈮，

本文編號：2451584