基于极小图的度量表示

《Discrete Mathematics》:Metric representations by minimal graphs

【字体: 大 中 小 】 时间:2026年10月23日 来源:Discrete Mathematics 1.1

编辑推荐:

   •实现坐标集且关于边集为极小的图。•判定一个集合是否能被有界大小的图实现是一个NP难问题。•具有唯一实现的坐标集的刻画。•可被树唯一实现的坐标集的刻画。 引言 Harary和Melter[6]关于图的度量维数的开创性论文首先回顾了取自Blumenthal经典著作[1]的度

  

•实现坐标集且关于边集为极小的图。•判定一个集合是否能被有界大小的图实现是一个NP难问题。•具有唯一实现的坐标集的刻画。•可被树唯一实现的坐标集的刻画。

引言

Harary和Melter[6]关于图的度量维数的开创性论文首先回顾了取自Blumenthal经典著作[1]的度量空间中基的定义。设S={v1,…,vn}为度量空间M中点的有序集合。点u的S坐标由其距离向量[d(u,v1),…,d(u,vn)]给出。集合S被称为M的度量基,若(1)M中没有任何两个点具有相同的坐标,且(2)不存在更小的集合满足(1)。作者随后指出,类似的定义适用于连通图,图上的度量坐标、度量基和度量维数概念由此产生。

Blumenthal的著作,正如第二章开头所述,讨论两点间距离具有不变性的几何性质,即作者所称的距离几何。换言之,其关注点在于空间中点之间的距离以及从这些距离中可以推断出什么性质。这一观点在度量空间和图中都已被广泛研究。

从连通图顶点间的距离来研究其性质的问题首次提出于[5],此后以多种方式加以研究。例如,[10]中的作者利用距离矩阵,考虑了通过叶结点间的距离集合来定义一棵树的问题,并证明如果这样的树存在,则它是唯一的。沿着这些思想,[11]中的作者建立了此类树存在的充要条件,并提供了构造算法。同样的问题也使用不同于树叶结点集合的其他顶点集进行了研究,这些顶点集在某种意义上可以表示图的"端点"。因此,[2]中的作者研究了如何从边界顶点间的距离来重构一个图。

我们对此问题的研究灵感来自Blumenthal的原始思想以及所谓的距离几何问题[7]:"在给定维度的向量空间中,是否存在一组点,使得其产生的给定子集成对距离与指定的点名对一一对应?"在本文中,我们研究可以从顶点度量坐标推断出的图的性质,这与[4]的出发点相似。

给定一个图G,分辨集是顶点的一个子集W?V(G),使得对任意一对不同的顶点u,v∈V(G),存在ω∈W能分辨这对顶点,即d(u,ω)≠d(v,ω)(参见[6],[9])。因此,每个顶点u∈V(G)可以由其相对于集合W={ω1,…,ωn}的度量坐标r(u|W)=(d(u,ω1),…,d(u,ωn))唯一标识。识别集合是否实际上为某个图的度量坐标集这一问题的提出,引发了"可实现性"这一概念。有限集S?Zn被称为由对(G,W)实现,其中G是图,W是分辨集,如果S={r(u|W):u∈V(G)}。[8]中对可实现集进行了刻画,作者还研究了n=2时实现唯一性的问题。

在本工作中,我们沿着这一研究方向继续进行。在第2节中,我们探索在什么条件下一种实现可以通过添加或删除一些边从另一种实现推导出来,这引导我们考虑极大和极小的实现,并刻画使得实现唯一的集合。此外,在第3节中,我们研究有关度量实现极小性的一个决策问题的计算复杂性。具体来说,就是给定一组距离向量和一个常数k,判定该集合是否可被至多有k条边的图实现。最后,在第4节中,我们专注于树的实现,刻画可被树实现的坐标集,以及此类实现的唯一性。

我们在本文中包含一些在余下部分中会用到的定义和已知结果。本文考虑的所有图都是有限且连通的。以下是图论中的标准概念。给定一个图G,具有顶点集V(G)和边集E(G),顶点u∈V(G)的邻域为NG(u)={v∈V(G):uv∈E(G)}。若u,v是G中不同的顶点且uv?E(G),我们定义G+uv为具有顶点集V(G+uv)=V(G)和边集E(G+uv)=E(G)∪{uv}的图。此外,若uv∈E(G),我们定义G?uv为具有顶点集V(G?uv)=V(G)和边集E(G?uv)=E(G)?{uv}的图。对于任意图G和H,映射f:V(H)?V(G)是H到G的等距嵌入,如果对任意u,v∈V(H)满足dG(f(u),f(v))=dH(u,v)。

**定义1**[3], [6], [9] 给定图G,顶点u∈V(G)相对于有序顶点子集W={ω1,…,ωn}?V(G)的度量表示为r(u|W)=(d(x,ω1),…,d(x,ωn))。图G的顶点子集W称为分辨集,如果对G中每对不同的顶点u,v∈V(G),u≠v,都有r(u|W)≠r(v|W)。

**定义2**[8] 子集S?Zn被称为可实现的,如果存在图G和G的分辨集W,使得S={r(u|W):u∈V(G)}。在这种情况下,我们称(G,W)是S的一个实现。

**定理3**[8] 子集S?Zn是可实现的,当且仅当满足以下性质:

1. 对于每个x∈S和每个i∈[n],xi≥0。此外,x至多有一个坐标等于零。
2. 对于每个i∈[n],存在恰好一个元素x∈S使得xi=0。
3. 如果x∈S且对于某个i∈[n]有xi>0,则存在y∈S满足yi=xi?1且max_{j∈[n]}{|yj?xj|}≤1。

**定义4**[8] 集合S?Zn的两个实现(G,W)和(G′,W′)是等价的,如果满足r(u|W)=r(f(u)|W′)的映射f:V(G)→V(G′)是一个图同构。

**定义5**[8] 设S?Zn是可实现的集合。S的典范实现为(G?,W?),其中

V(G?)=S,

E(G?)={xy:x,y∈S且max_{i∈[n]}|yi?xi|=1},

W?={x∈S:存在某个i∈[n]使得xi=0}。

典范实现在S的所有实现中起着核心作用,因为所有实现都可以被包含在典范实现中,方式如下。

**命题6**[8] 设(G,W)是S?Zn的一个实现。则映射?:V(G)→V(G?)定义为?(u)=r(u|W),是一个双射。此外,由V(G?)=V(G?)=S和E(G?)={?(u)?(v):uv∈E(G)}定义的G?的(不一定是诱导的)子图G?,提供了与(G,W)等价的S的实现(G?,W?)。

给定S的一个实现(G,W),命题6中定义的映射?显然是G到典范实现的一个生成子图之间的同构。因此,从现在起我们将集合S的所有实现都视为G?的生成子图,通过映射?将实现(G,W)与实现(G?,W?)等同起来。

注意映射?并不总是G到典范实现G?的等距嵌入,因为当u或v属于W时,dG?(?(u),?(v))=dG(u,v),但对于任意的u,v∈V(G),这一等式不一定成立。我们在下例中说明这些概念。

**例7** 集合S={(0,2),(1,1),(2,0),(1,2),(2,1),(2,2)}?Z2是可实现的,图1a显示了S的典范实现,图1b则显示了一个不等价的实现。两者均被描绘为P??P?的子图(参见[8])。在两种情况下,每个顶点的坐标是到W={(0,2),(2,0)}中顶点的距离。显然,第二种实现可以嵌入到典范实现中,但不是等距嵌入,因为在第一种情况下顶点(1,2)与(2,2)之间的距离为1,而在第二种情况下为3。

**章节片段**

**极小实现**

正如我们在第1节中所说明的,实现S的所有图都可以被视为S的典范实现(G?,W?)的生成子图。因此,典范实现的边集关于边集包含关系是极大的。本节目的在于研究S?Zn子集的极小实现,即这样的实现:移除其中一些边将产生一个不能实现S的图。在这些极小实现中,我们还关注确定哪些

**计算复杂性**

我们现在关注与向量集度量实现相关的若干决策问题的计算复杂性。我们从基本的实现问题开始。

**定义14** 我们定义度量实现问题METREL为以下决策问题:给定集合S?Z?,判定该集合是否可实现的。

利用定理3可知,METREL属于多项式时间可解类P,因为可实现的三个条件均可在多项式时间内轻松验证。此外,典范实现也可以

**树**

在研究S?Zn的极小实现的背景下,很自然地会问是否存在以树为形式的实现。因此,在本节中,我们专注于刻画可被树实现的集合。这一问题也出现在[4]中。

我们记S?={x∈S:(x??1,…,x???)∈S}和S?=S?S?。若x∈Z?且k≥1,我们记x?k=(x??k,…,x??k)。用此术语,S?={x∈S:x?1∈S}。在以下引理中,我们展示子集S?在集合S的树实现中所扮演的角色。

**引理17** 设S?Z?且假设

Víctor Franco-Sanchez|Mercè Mora|María Luz Puertas
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号