网络的路径分离数

发布时间：2019-04-01 13:20

【摘要】：在现实生活中,对于给定的一个互连网络,如何定位一个故障是一个广泛研究的问题,我们的想法是尽量利用较少的检测量去精确定位故障. 我们将遇到的这类问题转化成图论问题,进而研究与测试集十分相似的参数——路径分离数.图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)对benes网BB(n),有 (5)对网状网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