文摘

在计算机网络中,顶点代表主机或服务器,边代表它们之间的连接中。在定位,选择一些特殊的顶点(解决集)来定位计算机网络中的所有顶点的位置。如果任意顶点停止工作和选择顶点仍然解决集,然后选择集称为容错解决集。最少的顶点在这样解决集被称为网络的容错公制尺寸。因为各种各样的科学度量维度在不同领域中的应用,许多归纳提出了,容错就是其中之一。在这篇文章中,我们计算的容错度量维度三角蛇,阶梯,莫比乌斯梯,六角阶梯网络。观察是非常重要的,在所有这些类的网络容错度量维度和度量维度相差1。

1。介绍

让 是一个简单的连通图, 和 分别的顶点和边集。的距离 一对顶点之间 最短路径的长度是加入他们。一个顶点 解决或区分一对 如果 。的表示任意顶点 对应顶点的有序非空的子集 是 - - - - - -组件向量 。一个子集 如果任何一对被命名为解决集 拥有独特的条件表示, 。最不可能的基数 被命名为度量维度图的 和象征 。一套解决包含尽可能多的元素命名为基础。一套基础 的 叫做容错的基础设置,如果对于每一个吗 ,子集 再一次解决的顶点 。最少的顶点 称为的容错度量维度 和用 。乔杜里et al。1)是一种重要的容错度量维度和度量维度之间的关系图 。

第一次,度量维度研究了斯莱特(2)1975年,后来通过Harary和熔炼工(31976年)。沙特朗et al。4)度量基地视为传感器。如果任何传感器的不正确操作,我们没有足够的知识来应对入侵者。Hernando et al。5]介绍了容错的概念度量维度来克服这种问题。容错的基础上设置提供了准确的信息虽然是一个传感器不工作。由于不同的应用程序,研究不同网络的容错解决集一样的度规的研究维度。

这是证明了计算度量维度是np完备性6]。然而,独特的识别图中的每个顶点的概念基于距离是非常有用的。这一概念的应用在化学结构提出了沙特朗el al。4]。在机器人导航,通过奇et al。7]动机理论的研究人员调查的指标维度。解决集发现许多应用程序。更多细节,请参阅[8- - - - - -10]。一般来说,计算容错度量维度也是一个np完全问题。计算容错度量维度被认为是一个有趣的但在组合数学难题。到目前为止,只有少数结构进行了调查。在最初,Hernando et al。5)计算容错组树的基础 。对于一个图 ,他们得到一个容错度量维度和度量维度之间的联系,也就是说, 。Javaid et al。11)研究了该参数的循环图 并讨论了一些界限划分维度。更多相关结果容错度量维度,有兴趣的读者可以看到[12- - - - - -23]。

本文的核心目标是找到图满足方程的一些类 。它已被观察到,如果 是阶梯 ,默比乌斯梯 ,和六角莫比乌斯梯图 ,然后度量维度和容错公制尺寸相差1。也为三角形,蛇图 ,上述平等成立当且仅当 。为了证明这些结果,我们需要一些文献的结果。

定理1。(见[4])。图1敌我识别的指标维度 。

定理2。(见[24])。让 是一个莫比乌斯梯图。然后,

定理3。(见[25])。让 是一个六角形的莫比乌斯梯图。然后,

定理4。(见[5])。让 是一个阶梯图 。然后,

2。三角蛇的容错度规尺寸图

本节涉及的度量维度和容错度量维度三角蛇图。让 与顶点的路径集 ,在哪里 是一个奇数。一个三角形的蛇图 是由 通过连接 与 为 。请注意, 代表三角形的基数 。三角蛇图如图1。下面的引理1,我们计算度量维度 三角形的蛇图 。


图1
三角蛇图 。

引理1。让 是一个三角蛇图 。然后,

证明。从定理1,接下去 。证明 ,我们证明 。让 是一套解决。然后,顶点的表征 关于解决集 如下: 因为所有的顶点有独特的关于解决集表示 ,因此, 。

定理5。让 是一个三角蛇图;然后,

证明。首先,我们证明 当 。为了证明这一点,这就足以证明 。的不平等 遵循从引理1与方程(1)。如果我们把 ,然后满足条件的容错解决。以下是任何顶点的表示 图的 关于 : 在哪里 当 和零,否则。
现在,我们证明 当 。为此,我们构建一套容错解决。 ;以下是任何顶点的图的表示 : 在哪里 为 和零,否则。因此,由上列的讨论 因为每个顶点 一套独特的表示关于解决吗 。
我们证明相反的不平等 矛盾的方法。假设 ,它遵循从引理1那 。让我们考虑一些解决集 基数3。

案例1。让 ,在哪里 。如果我们选择 ,然后 。对于任何其他的选择 ,我们得到了 。

例2。让 或 ,在哪里 和 。换句话说,我们正在采取的第一个顶点第一个三角形和其余任意三角形的顶点。然后,很容易观察到存在一个整数 这样 。

例3。让 ,在哪里 。然后, 。
因此,由上列的讨论 当 。这意味着 当 。这就完成了证明。

3所示。容错度量维度的梯形图

梯子图的笛卡儿积得到的路径 与路径 和用 。观察到 。梯子图如图2。在下面的定理,我们计算的容错度量维度梯子图。


图2
梯形图 。

定理6。让 是一个阶梯图 。然后,

证明。的不平等 遵循从定理4与方程(1)。为了证明 ,我们构建一套容错解决。 ;然后,任何顶点的表示 的图 可以计算为 在哪里 为 和 为 和零,否则。观察到的所有顶点 有一个独特的代表关于容错组吗 。因此, 。
莫比乌斯梯是首次由理查德·盖伊和弗兰克Harary [26]。这是一个三个正常图由一个循环 通过加入顶点 周期的敌我识别 。默比乌斯梯有偶数个顶点。它是用 ,在哪里 。满足这个条件被称为对映的顶点。默比乌斯梯图的图所示3。莫比乌斯梯子有几个使用不同的立体化学等科学领域,计算机网络,电工学。在接下来的结果,我们发现容错度量维度的莫比乌斯梯。


图3
默比乌斯梯图 。

定理7。让 是一个莫比乌斯梯图。然后,

证明。让 是一个偶数。的不平等 遵循从定理2与方程(1)。为了证明 ,我们构建一套满足容错度量维度的定义。让 ;然后,任何顶点的距离 相对应的图 可以计算如下。
顶点的距离 从顶点 是 顶点的距离 从顶点 是 顶点的距离 从顶点 是 顶点的距离 从顶点 是 因为所有的顶点 有独特的表现对于解决吗 ,因此, 。
现在,让 是一个奇数。证明 ,我们构建一套解决满足容错度量维度的状况。让 ;然后,任何顶点的距离 从顶点 ,和 如下。
顶点的距离 从顶点 是 顶点的距离 从顶点 是 顶点的距离 从顶点 是 因为所有的顶点 有独特的表达关于决定解决集吗 ,因此, 。
一个六角莫比乌斯梯 由细分每个平方晶格的水平边缘;因此,我们得到一个格子,每个周期订单6;在创建这个格子,扭转最近获得的晶格 并加入最左和右顶点如图4。六角莫比乌斯梯 包含 水平和 垂直循环。让 是一个六角形的莫比乌斯梯 水平垂直循环周期和1。在接下来的定理,我们计算的容错度量维度 。


图4
六角莫比乌斯梯图 。

定理8。让 是一个六角形的莫比乌斯梯图。然后,

证明。让 ;的不平等 遵循从定理3与方程(1)。为了证明 ,我们构建一套满足容错度量维度的定义。让 ;然后,任何顶点的距离 相对应的图 可以计算如下。
顶点的距离 从顶点 是 顶点的距离 从顶点 是 顶点的距离 从顶点 是 很容易看到,每个顶点 有其独特的代表性的解决 。因此, 。
让 ;证明 ,它足以构建一个容错解决组四个元素满足容错度量维度的状况。让 ;然后,任何顶点的距离 的 与 可以计算如下。
顶点的距离 从顶点 是 顶点的距离 从顶点 是 顶点的距离 从顶点 是 顶点的距离 从顶点 是 很容易看到的所有顶点 有独特的交涉关于解决吗 。因此, 。

4所示。结论

在本文中,我们研究三角蛇的容错度规尺寸图,阶梯,莫比乌斯梯,六角莫比乌斯梯。众所周知,对于周期图 ,我们有 。因此,有趣的是找到一些类图的这个等式成立。注意,在三角蛇图,阶梯,莫比乌斯梯,和六角莫比乌斯梯,我们有 。

数据可用性

没有数据被用来支持本研究。

信息披露

进行这项研究的作者们的就业。

的利益冲突

作者宣称没有利益冲突。