论文部分内容阅读
在现实生活中，对于给定的一个互连网络，如何定位一个故障是一个广泛研究的问题，我们的想法是尽量利用较少的检测量去精确定位故障. 我们将遇到的这类问题转化成图论问题，进而研究与测试集十分相似的参数——路径分离数.图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的路径分离数(记为psn(G))是分离集中拥有的小路径个数（记|P|）.psn(G)=min{|P|:P是图G的路径分离集} 本篇文章主要研究了一些图类的路径分离数问题.在猜想psn(G)=O(n)的基础上，根据目前已有的方法、结论以及新的方法对一些特殊图类（如Halin图，轮图，网络拓扑结构图）的路径分离数进行研究. 本文主要的结果如下: (1)对n≥3阶的圈Cn，有psn(Cn)=n; (2)对Halin图Hn，有psn（Hn）≤k+2; (3)对轮图Wn(n≥5)，有psn(Wn)=n; (4)对bene(s)网BB(n)，有4n ln n2n+2/(2n+1)lne(2n+1)2n-1≤psn(BB(n)）≤(8n-3)2n-1; (5)对网状网G（l，m）l，m≥3，有psn(G(l，m)）≤{2(m+l-1)|l-m|≤22(m+l-2)+|l-m||l-m|＞2.