度量维数介绍与具体应用

2522可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）111-123www.elsevier.com/locate/entcs度量维数：从图到有向图Julien Bensmaila，1，4 Fionn Mc Inerneya，2，4 Nicolas Nissea，3，4a蔚蓝海岸大学摘要一个无向图G的度量维数MD（G）是一个最小的顶点集的基数，该顶点集允许通过它们到所有顶点的距离来区分G的任何两个顶点。自70年代引入以来，这个概念的许多方面都得到了研究在这项工作中，我们研究，对于特定的图族，在所有强连通方向上的最大度量维数，通过展示这个值的上下界。我们首先展示了具有有界最大度的图的一般界。特别地，我们证明了，在次立方n-节点图的情况下，所有的强连通方向渐近地具有至多n的度量维数，并且存在是具有度量维度2n的这种取向。然后，我们考虑强连接方向的网格。对于n行m列的环面，我们证明了强连通欧拉定向的度量维数的最大值是渐近的nm（当n，m为这是最好的可能）。对于n行m列的网格，我们证明了所有的强连通方向渐近地具有至多2nm的度量维数，并且存在这样的方向，3公制尺寸nm。保留字：分解集，度量维数，强连通方向。1介绍1.1无向图的分解集与度量维数无向图G的两个顶点u，v之间的距离distG（u，v）（或当不可能有二义性时简称为dist（u，v））是从u到v的最短路径的长度。 G的一个分解集R是允许区分G的所有顶点根据它们到R的顶点的距离。 换句话说，R是可解的当且仅当，对于G的每两个不同的顶点u，v，1电子邮件：julien. inria.fr2电子邮件：fionn. inria.fr3电子邮件：nicolas. inria.fr4这项工作得到了ANR项目MultiMod和ANR计划“未来投资”的部分支持，参考编号为ANR-11-LABX-0031-01。由于篇幅所限，这里只简略地列举了几个证明完整的证明可以在https://hal.inria.fr/hal-01938290上找到https://doi.org/10.1016/j.entcs.2019.08.0111571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。112J. Bensmail et al. /Electronic Notes in Theoretical Computer Science 346（2019）111w∈R使得distG（w，u）= distG（w，v）. G的度量维数MD（G）是G的一个分解集的最小基数。 由于V（G）\{v}是G的一个分解集，对于每个v∈V（G），这个参数MD（G）被定义为每个无向图G。自Harary和Melter [ 8 ]和Slater [ 14 ]在70年代引入以来，分解集和度量维数的概念已经得到了广泛的研究，特别是因为它们可以用来模拟许多现实生活中的迄今为止，许多相关方面已经被研究，包括算法和复杂性方面，以及特定图族的度量维度的界限。我们在这篇论文中的主要焦点是有向图的度量维数，我们建议感兴趣的读者阅读调查（例如[1，2]）以获得更多关于无向上下文中调查的细节。1.2有向图的分解集与度量维数推广图论问题的一个自然方法是考虑它们的直接对应物。在图的度量维数的上下文中，这首先由Chartrand，Rains和Zhang在[3]中考虑，然后在几部作品中得到进一步的考虑（见[5，6，9，11，12]）。值得回顾的是，在有向图中，距离的行为与无向图中的行为不同。值得注意的是，应该解决的一个重要问题是，在一般有向图D的上下文中，对于任何两个顶点u，v，我们可能有dist（u，v）/= dist（v，u），其中dist（u，v）在这里指的是从u到v的最短有向路径的长度。一个有向图D是强连通的（或简称强连通），如果对每个u，v∈V（D），有一条从u到v的有向路，反之也有一条从v到u的有向路。因此，如果D不强，则存在顶点u，v∈V（D）使得不存在从u到v的有向路。 在这种情况下，我们设置dist（u，v）=+∞。在定义分解集和度量维数的有向概念时，必须考虑有向图中距离的这些特殊方面在整个工作中，有向图中的分解集和度量维数的概念与以下定义有关。设R是有向图D的顶点子集。D的两个顶点u，v被称为是可区分的，记为uRv，如果存在w∈R使得dist（w，u）/= dist（w，v）.否则，u和v不被R区分，记为u<$Rv。特别地，如果dist（w，u）是有限的，并且dist（w，v）对于某个w∈R不是，则uRv。一个集合R∈V（D）称为可解的，如果D的所有顶点对都可由R区分。D的度量维数MD（D）则是一个分解集的最小尺寸。注意，对于每个有向图D定义了MD（D）;特别地，我们有MD（D）<|V（D）|因为R=V（D）\{v}是任何v∈V（D）的分解集（因为在分解集中有任何顶点使其与所有其他顶点区分开）。我们的有向分解集和度量维数的定义实际上不同于最初由Chartrand，Rains和Zhang引入的定义。一方面，在他们对分解集的定义中，他们考虑了从每个不在R中的顶点到R中的顶点的距离，以便区分D的顶点。J. Bensmail et al. /Electronic Notes in Theoretical Computer Science 346（2019）111113˜˜在我们的定义中，考虑了从R中的每个顶点到不在R中的顶点的距离。请注意，这两个定义在这一点上是等价的，因为，给定一个有向图D，如果我们反转所有弧的方向，得到一个有向图D，那么D中从u到v的任何最短路径都成为D中从v到u的最短路径。另一方面，他们对分解集的定义要求定义从每对不同顶点到R中区分它们的顶点的距离，而我们的定义（从R中的顶点到其他顶点的距离）也允许使用未定义的距离（+∞）。与我们的定义相反，这意味着他们对度量维数的定义并不适用于所有有向图。据我们所知，允许度量维数的有向图的特征（根据它们的定义）仍然是一个开放的问题[3]。尽管我们的定义与Chartrand、Rains和Zhang的定义不同，但值得一提的是，我们在本文中的大部分研究也适用于它们的上下文，因为我们主要关注强有向图，在这种情况下，我们的定义和他们的定义是等价的（直到反转所有弧）。到目前为止，对有向图的度量维数的研究一直是关于最初由Chartrand，Rains和Zhang引入的定义。作为第一步，他们在[3]中给出了度量维数为1的有向图的一个特征。在[12]中考虑了复杂性方面，其中证明了确定强有向图的度量维数是NP-完全的。各种有向图族的度量维数的界后来被展示出来（Cayley有向图[5]，线有向图[6]，竞赛图[9]，具有循环覆盖的有向图[11]，De Bruijn和Kautz有向图[12]等）。1.3从无向图到有向图为了避免任何混淆，让我们回想一下，当G的每条边uv从u到v定向（导致弧（u，v））或相反（导致弧（v，u））时，可以获得无向图G的定向D。定向图D是作为简单图的定向的定向图。注意，当G是单的时，D不能有两个顶点u，v使得（u，v）和（v，u）是弧。这种对称弧在有向图中是允许的，这是定向图与有向图的主要区别。在本文中，当简单地提到一个图时，我们指的是一个无向图。在[4]中，Chartrand，Rains和Zhang考虑了以下连接无向图和有向图的分解集的方法。他们认为，对于一个给定的图G，最坏的方向G的度量维数，即， G的最大度量维数的方向。看看我们对分解集和度量维数的定义，这是一个合理的问题，因为必须指出，对于一个图，在定向它的边时，度量维数可能会或可能不会保持。一个有趣的例子（例如， [3]（9）图G具有哈密尔顿路径：虽然MD（G）通常可以是任意大的（考虑例如，任何完全图），存在G的方向D，验证MD（D）= 1（仅将Hamilton路径的所有边从第一个顶点朝向114J. Bensmail et al. /Electronic Notes in Theoretical Computer Science 346（2019）11125∈ GWOMD（G）2最后一个顶点，以及相反方向上的所有剩余边相反地，存在G的取向D，其中MD（D）可以比MD（G）大得多。 作为 例如，让我们考虑具有2n + 1个顶点v0，.，v2;显然，MD（P）= 1;然而，通过使每个顶点v2k +1（k = 0，.，n-1）成为源（即，使其入射边远离）验证MD（D）=n。如本文所示，这种现象也发生在强取向。在[4]中，作者证明了：对于任意正整数k，存在无限多个图，其任意强连通方向的度量维数恰好为k。他们还证明了不存在常数k使得任何锦标赛的度量维数至多为k。1.4我们的结果受这些观察的启发，我们在整个工作中研究了定义如下的参数WOMD。对于任意连通图G，设WOMD（G）表示G的所有强定向D上MD（D）的最大值.让我们将这个定义扩展到图族，如下所示。对于任意2-边连通图族G，设WOMD（G）= max.第二节首先介绍了工具和重新设计。G∈G|V(G)|这些结果将在下一节中使用。第三节证明了WOMD（GΔ）的界，其中GΔ是指具有最大度Δ的2-边连通图族特别地，我们证明了渐近地有2≤WOMD（G3）≤1.在第4节中，我们考虑网格族和环面族。对于家庭Ttori，我们证明我们渐近有WEOMD（T）=1，其中参数WEOMD（T）的定义类似于WOMD（T），除了只有强欧拉方向的tori（即，所有顶点都具有入度和出度2）。对于网格族G，我们证明了渐近1≤WOMD（G）≤2。2 3剩余的未决问题和难题收集在第5节中。术语和符号设D是一个有向图。对于D的顶点v，我们用d−（v）（resp.d+（v））D D入度（resp. （v）是一个数，是一个数，是一个数。（即将离任）与v相关联的弧对于每个弧（v，u）（分别为（u，v））进入（resp.从你出去，我们称你为外邻居（分别）。（v）相邻的。所有内邻居的集合（分别为v的外邻（out-neighbors）表示为N−（v）（resp.N+（v））。的D D当不可能有歧义时，可以删除前面符号中的下标我们用Δ+（D）（分别，Δ−（D））最大出度（分别为，最大入度）。注意，在有向图D中，入度（相应地，一个顶点的出度（out-degree）对应于它的内邻域的基数（resp.外邻）。5边连通性要求，在这里和进一步，是为了保证对每个GΔ的WOMD（G）的良好定义，因为众所周知的事实是，一个图具有强定向当且仅当它是2-边连通的（参见[13]）。J. Bensmail et al. /Electronic Notes in Theoretical Computer Science 346（2019）1111152工具和初步结果我们首先指出具有相同内邻域的顶点的有向图的分解集的以下性质。这一结果将是我们构造大度量维数有向图的主要工具引理2.1设D是有向图，S ∈ V（D）是|S| ≥ 2个顶点，使得对于每个u，v∈S，我们有N−（u）= N−（v）。那么，D的任何分解集至少包含|S| S的1个顶点。证据 若两个顶点u，v ∈ S不属于一个分解集R，则对任意的w ∈ R，dist（w，u）= dist（w，v），这与R是一个分解集是矛盾的。Q我们现在介绍一种技术，将在下一节中用于展示最大出度至少为2的强有向图的度量维数的上界图G的顶点覆盖是顶点的子集S∈V（G），使得对于G的每条边uv，u和v中至少有一个属于S。 对于任何有向图D，我们将一个辅助图（无向）图Daux构造如下：Daux的顶点是D的顶点;对于D的每两个不同的顶点u，v，使得ND−（u）<$ND−（v）/=N，让我们将边uv添加到Daux。 换句话说，Daux是一个简单无向图，D的不同顶点对共享内邻。通过构造，请注意，在Daux中，每两个不同的顶点最多由一条边连接证明了对于最大出度至少为2的强有向图D，Daux的一个点覆盖在D中是可分解的。引理2.2设D是强有向图，且Δ +（D）≥ 2。D aux的任意顶点覆盖是D的分解集。证据 面对矛盾，假设这个主张是错误的，即，存在一组S∈V（D）是Daux的一个点覆盖但不是D的一个分解集.当Δ+（D）≥2时，D aux中有一条棱，且S=//-是的Letv1，v2是两个不能通过它们与S的距离来区分的顶点;换句话说，对于对于每个w∈S（注意w v1，v2），我们有distD（w，v1）= distD（w，v2），并且距离有限，因为D是强的。现在考虑这样一个顶点w∈S在最小v1和v2之间的距离。在D中，从w到v1的任何最短路径P1与从w到v2的任何最短路径P2具有相同的长度。因为v1/=v2和P1，P2是最短路径，注意P1和P2的所有顶点不可能相同;因此让x1表示P1的第一个不属于P2的顶点，同样地，让x2表示P2的第一个不属于P1的顶点。换句话说，P1和P2的第一个顶点在某个顶点x上重合，但接下来的顶点x1（在P1中）和x2（在P2中）是不同的。所以Daux包含边x1x2，并且x1，x2中至少有一个属于S。此外，x1和x2比w更接近v1，v2;这与w的原始选择相矛盾。Q引理2.2表明，通过考虑每个顶点并选择116J. Bensmail et al. /Electronic Notes in Theoretical Computer Science 346（2019）111∗|||J一KBLCRR'一MBnCOODMenFDpeQFRRGpHQ我GKHL我J（一）（b）第（1）款图1.一、（a）有向图D3，3，2. 红顶点的集合是最优解集的一个例子。（b）6个中的一个强定向D6环面T6，6维MD（D）=V（T6，6）/2。 每两个标记有相同字母的顶点具有相同的内邻域;因此，每一个分解集必须至少包含其中之一。除了一个外，至少是所有的外邻居。证明表明，这是因为这是一种区分从一个顶点到其他顶点的所有最短路径的方法推论2.3对任意强有向图D，Δ+（D）≥2，D的MD（D）至多是D aux的最小顶点覆盖的大小。不幸的是，确定给定图的顶点覆盖的最小尺寸一般是NP完全问题[7]。然而，在推论2.3的上下文中，我们最感兴趣的是Daux的最小顶点覆盖的大小的合理上界。当D具有特定的附加性质时，可以表现出这样的上界，这将在下一节中显示3最大度有界的强定向图通过给定有向图D的最大度Δ（D），我们指的是其底层无向图的最大度（即，d−（v）+d+（v）在D的顶点v上的最大值）。在本节中，我们研究了在给定最大度的图的所有强方向D中MD（D）所能取的最大值。由于Δ（D）= 2的强定向图D是一个有向圈，在这种情况下 MD（D）平凡地为1，因此我们主要研究Δ（D）≥3的情况我们在本节中的所有下界都是通过以下步骤得到的。对任意k∈N，Δ≥ 2，我们用TΔ，k表示深度为k的有根Δ-元完全树.更准确地说，TΔ，k是一棵有根树，使得每个非叶子顶点都有Δ个孩子，并且所有叶子都离根距离k注意|V(TΔ,k ） =Δk+1−1和TΔ−1Δ，k有Δk个叶子，最大度为Δ + 1。任何k∈N且Δ，i≥ 2，设DΔ，k，i为定向图，定义如下（见图-J. Bensmail et al. /Electronic Notes in Theoretical Computer Science 346（2019）111117≤ ≤ − ≤≤···J···Jn.1Δk−11我JL我1Δ1图1a为说明）。开始时T是TΔ，k−1的副本，所有边从根到叶。设vk−1，···，vk−1是T的叶子，R是它的根。 对于每一个1 ≤j≤Δ k−1，将i的外邻居uj，···，uj与vk−1相加。然后，对于1 ≤ j ≤ Δ k−1和1 ≤ l 0，2 15−ω≤WOMD（G3）≤2，12−ω≤WOMD（G4）≤6，lim7Δ→∞WOMD（GΔ）=1。4网格和环面通过网格Gn，m，我们指的是两条路径Pn，Pm的笛卡尔积PnQPm。环面Tn，m是两个圈Cn，Cm的笛卡尔积CnQCm。在无向上下文中，很容易看出MD（Gn，m）= 2而MD（Tn，m）= 3（参见例如，[10]）;然而，在定向上下文中，事情变得有点棘手网格和环面的最大度为4;因此，强定向网格或环面的最大度量维数的界可以从我们在第3节中的结果导出。 在本节中，我们通过专门的证明来改进这些界限，120J. Bensmail et al. /Electronic Notes in Theoretical Computer Science 346（2019）1112222nmWEOMD（G）nm争论我们首先考虑强欧拉定向环面（所有顶点的入度和出度都是2），我们展示了度量维度的最大值。然后，我们考虑强定向网格，我们提供了改进的边界。4.1环面的强欧拉定向设0 0，我们有1 22−ω≤ WOMD（G）≤3 + ω。证据的草图。让我们考虑网格Gn，m的情况，当n和m是偶数时。我们首先证明了存在Gn，m的强取向D，使得MD（D）≥nm−（n+m）.事实上，让我们类似于定理4.1（和图1b）中的Tn，m来定向Gn，m下界由引理2.1得出，因为顶点可以是被划分为具有公共内邻域的坏顶点对（除了边界上的顶点（第一/最后一行/列），在这种情况下，只有一半的顶点被包括在坏顶点对中）。对于上界，让我们假设m0 mod 3。 该证明是有效的，并提供了一个最大为2nm+λ的分辨率集。该算法从集合R ={V（Gn ，m）\（i，3 j− 1）|0 ≤i≤n-1，1≤j≤m/3}（即， R包含网格中从左到右每3列中的前2列），并迭代地执行局部修改（将R中的一个顶点与其不在R中的一个相邻顶点交换），而不改变R的大小，直到R成为一个解析集R。确切地说，如果R不是一个分解集（否则，我们就完成了），那么至少有两个顶点是不能通过它们到R中顶点的距离来区分的。设u和v为2 这样的顶点。证明了对于任意两个顶点u和v，它们属于同一列C（不包括R中的任何顶点），且存在唯一的顶点w∈C（称为u和v的最后公共顶点（LCV））在相同的距离nuuvnvununvvuaa一XzWQByBbv122J. Bensmail et al. /Electronic Notes in Theoretical Computer Science 346（2019）11123≥45从u和v（见图2b，其中省略了上标w）。在这种情况下，设zw是w左边的顶点，xw是w上面的顶点，aw是xw左边zw上面的顶点，bw是zw下面的顶点。 我们证明了，对于每一个LCV w，顶点{w，zw，aw，bw}和它们周围的顶点是成对顶点不相交的。最后，我们证明了（通过一个冗长的例子分析）顶点集R是一个分解集，其中R是通过对每个LCV w交换顶点zw和xw（如果（aw，zw）或（bw，zw）是弧）或交换顶点aw和xw而从R得到的.Q5结论在这项工作中，我们已经调查，为几个家庭的图，最坏的强定向的度量维数。在特定的设置中，例如当考虑环面的强欧拉方向时，我们设法确定最坏的可能方向（定理4.1）。对于其他的家庭（图有界的最大度和网格），我们已经展示了上下限和WOMD或多或少的距离。作为这个主题的进一步工作，减小我们的上界和下界之间的差距，或者考虑其他图族的强定向将是有趣的。特别是，两个有吸引力的方向可能是改进推论3.4（对于max。 （3）定理4.2。对于最大度为3的图，我们确实想知道是否存在度量维数大于两个顶点。也可以合理地问，我们的上界（1的顶点），这是从推论2.3中描述的简单技术获得的，可以进一步降低。在定理4.2中，我们证明了网格的任何强定向公制维数最多为2的顶点。为了改善这个鞋面如果有约束，可以考虑应用推论2.3，例如如下。对于一个给定的定向网格D，设A是如下得到的图（其中我们使用与第4节相同的术语来处理D的顶点）：• V（A）=V（D）。• 在A中，我们在两个顶点（i，j）和（iJ，jJ）之间加上一条边，如果它们在D下面的网格中由一条长度正好为2的路径连接。也就是说，每当（iJ，jJ）具有（i-1，j- 1）、（i-2，j）、（i-1，j + 1）、（i，j+ 2）、（i+1，j +1）、（i+2，j）、（i+1，j- 1）或（i，j-2）的形式时，添加边注意，A的两个连通分量C1、C2基本上是通过沿边粘接K4有关说明，请参见图3可以注意到，对于任何有向网格D，其辅助图Daux是Aaux的子图。由推论2.3可知，A的最小顶点覆盖的大小的任何上界因此也是MD（D）的上界（假设D是强的，在这种情况下它必然证明Δ+（D）2）。不幸的是，我们已经观察到A的任何最小顶点覆盖覆盖了3个顶点，这并不好比定理4.2中的上界大J. Bensmail et al. /Electronic Notes in Theoretical Computer Science 346（2019）111123嗯？22（a）G9、9（b）A、9（c）C1(d)C2图3.第三章。 网格G9，9和关联图A。然而，仍然有希望使用顶点覆盖方法来提高我们的上限事实上，在假设D是一个强定向图的情况下，实际上Daux可以远远不具有Aaux所具有的所有边。例如，可以很容易地证明，在Daux中，顶点（i，j）不可能与所有四个顶点（i − 2，j），（i，j +2），（i +2，j），（i，j − 2）相邻（如果它们存在）。 使用计算机，我们实际上能够检查小网格，对于所有强方向D，Daux的最小顶点覆盖的大小最多为1个顶点。这导致我们提出以下两个与定理4.2中的上界有关的问题：问题5.1对于任意强定向的网格Gn，m，Daux的最小顶点覆盖的大小是否至多为nm？问题5.2对于网格Gn，m的任意强定向D，是否有MD（D）≤2注意，如果问题5.2中的上限成立，那么它将接近Th中的下限。 4.2.引用[1] R.F. 贝利，P.J.卡梅隆。 群与图的基大小、度量维数及其它不变量。Bulletin of the London Mathematical Society，43：209-242，2011.[2] G.沙特朗湖Eroh，M. Johnson，O.奥勒曼图的可分解性与度量维数一个graph。离散应用数学，105（1-3）：99-113，2000.[3] G. Chartrand，M.雷恩斯，张鹏。有向图的有向距离维数。Math. Bohemica，125：155-168，2000.[4] G. Chartrand，M.雷恩斯，张鹏。关于有向图的维数。Utilitas Mathematica，60：139- 151，2001.124J. Bensmail et al. /Electronic Notes in Theoretical Computer Science 346（2019）111[5] M. Fehr，S. Gosselin，手术室奥勒曼Cayley有向图的度量维数。离散数学，306：31-41，2006年。[6] M.冯，M. Xu，K.王.关于线图的度量维数。离散应用数学，161：802-805，2013年。[7] M.R. Garey，D.S.约翰逊计算机与难处理性：NP完备性，1990年。[8] F. Harary，R.A.融化。关于图的度量维数Ars Combinatoria，2：191195，1976.[9] A.洛萨诺Tourist中的对称破缺The Electronic Journal of Combinatorics，20（1）：Paper #P69，2013.[10] P. Manuel，B.拉詹岛Rajasingh，M.C.莫妮卡环面网络中的地标。Journal of Discrete MathematicalSciences and Cryptography，9（2）：263-271，2013.[11] S. 潘卡哈亚尼河西曼君塔克具有循环覆盖的有向图的有向度量维数Journal of Combinatorial Mathematics and Combinatorial Computing，94：15-25，2015.[12] B.拉詹岛Rajasingh，J.A.辛西娅，P.曼纽尔。有向图的度量维数。International Journal of ComputerMathematics，91（7）：1397-1406，2014.[13] 阁下罗宾斯图的一个定理及其在交通控制问题中的应用。Am.数学。数学。，46：281283，1939.[14] P.J. 斯莱特树叶第549559页。第一次，不。1975年第十四期