【摘要】：在現(xiàn)實(shí)生活中,對(duì)于給定的一個(gè)互連網(wǎng)絡(luò),如何定位一個(gè)故障是一個(gè)廣泛研究的問題,我們的想法是盡量利用較少的檢測(cè)量去精確定位故障. 我們將遇到的這類問題轉(zhuǎn)化成圖論問題,進(jìn)而研究與測(cè)試集十分相似的參數(shù)——路徑分離數(shù).圖G的路徑分離集是路的集合P={P1,...,Pt},其中P1,...,Pt(?)G,對(duì)任意一對(duì)邊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))是分離集中擁有的最小路徑個(gè)數(shù)(記|P|).psn(G)=min {|P|:P是圖G的路徑分離集} 本篇文章主要研究了一些圖類的路徑分離數(shù)問題.在猜想psn(G)=O(n)的基礎(chǔ)上,根據(jù)目前已有的方法、結(jié)論以及新的方法對(duì)一些特殊圖類(如Halin圖,輪圖,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖)的路徑分離數(shù)進(jìn)行研究. 本文主要的結(jié)果如下： (1)對(duì)n≥3階的圈Cn,有psn(Cn)=n； (2)對(duì)Halin圖Hn,有psn(Hn)≤k+2； (3)對(duì)輪圖Wn(n≥5),有psn(Wn)=n； (4)對(duì)benes網(wǎng)BB(n),有 (5)對(duì)網(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 鈮，

本文編號(hào)：2451584