【摘 要】
：
图的分辨集是在1970年代由Slater,Harary和Melter分别独立提出.若S是图G的分辨集,则对于任意一对点u,v∈V（G）,都存在x∈S,使得dG（u,x）≠dG（v,x）.最小的分辨集的大小也被称为图的度量维数,求解图的最小的分辨集的大小的问题被称为度量维数问题.图的2-分辨集则是Cáceres等为了解决笛卡尔积图上的度量维数问题所提出来的.若S是阶数至少为2的连通图G的2-分辨集,
论文部分内容阅读
图的分辨集是在1970年代由Slater,Harary和Melter分别独立提出.若S是图G的分辨集,则对于任意一对点u,v∈V（G）,都存在x∈S,使得dG（u,x）≠dG（v,x）.最小的分辨集的大小也被称为图的度量维数,求解图的最小的分辨集的大小的问题被称为度量维数问题.图的2-分辨集则是Cáceres等为了解决笛卡尔积图上的度量维数问题所提出来的.若S是阶数至少为2的连通图G的2-分辨集,则对于任意一对点u,v∈V（G）,都存在x,y∈S,使得dG（u,x）-dG（u,y）≠dG（v,x）-dG（v,y）.我们用Ψ（G）表示图的最小2-分辨集的大小.求解图的最小的2-分辨集的大小的问题被称为（最小）2-分辨集问题.本文主要研究特殊图上的2-分辨集问题.我们首先研究了k-边增树的2-分辨集问题.我们证明了若G是一个k-边增树满足δ（G）≥2,则Ψ（G）≤2k+1.此外,我们证明了若G存在割点或者k=2,则Ψ（G）≤2k,并且这个结果是紧的.对于满足δ（G）≥2的2-边增树G,我们刻画了这类图Ψ（G）的取值,并给出了一个线性时间算法求得Ψ（G）.接下来,我们研究了汉明图、超立方体和折叠超立方体的2-分辨集问题.我们证明了超立方体的2-分辨集问题与硬币称重问题完全等价,并由此回答了超立方体的2-分辨集问题中的一个公开问题.通过建立各个问题之间的联系,我们给出了汉明图的2-分辨集问题和折叠超立方体的度量维数问题的渐近解,并推翻了折叠超立方体的度量维数问题的一个猜想.通过与Lindstr?m提出的求解硬币称重问题的方法进行联系,我们给出了一个求解超立方体的2-分辨集问题的有效算法,并给出了一些新的硬币称重问题的上界和超立方体的度量维数问题和2-分辨集问题的上界.此外,我们研究了线图上的2-分辨集问题.我们给出了树的线图的最小2-分辨集大小的公式,由此说明存在一个线性时间算法求解树的线图上的2-分辨集问题.我们给出了线图的最小2-分辨集大小的上下界,并且上下界都是紧的.最后,我们证明了2-分辨集问题是NP-难的,即使限制在分裂图、二部图、余二部图和二部图的线图上.
其他文献
定量髓鞘水成像（Myelin Water Imaging,MWI）通过磁共振成像（Magnetic Resonance Imaging,MRI）方法得到髓鞘水分数（Myelin Water Fraction,MWF）,在神经和精神疾病的诊断和研究中具有重要的价值。然而,传统的基于多回波梯度回波序列（multiple Gradient Recalled Echo,mGRE）的MWF计算过程通常需要耗
水资源短缺,尤其是淡水资源的短缺,是近年来最为严峻的问题之一,已经严重影响到人类生活和生产的进行。电容去离子技术（Capacitive deionization,CDI）作为一种新型的脱盐方式,已经获得人们的广泛关注。由于其操作简便、成本低、能耗低、环境友好等优势,在海水淡化、资源提取、重金属去除等方面发挥出巨大的作用。然而,传统的CDI受限于材料与器件的影响,在实际生产中面临着循环稳定性不足和脱
近年来,奇摄动系统广泛地应用于建立流体力学、化学反应、生物学等自然科学和工程技术中的相关模型.然而,这些模型经常是在定义域内某条曲线处间断,即不连续奇摄动系统,或者是具有多个小参数,即多尺度快慢系统.因此,越来越多的科研工作者关注于不连续奇摄动系统和多尺度快慢系统的研究中,并极大地丰富和发展了奇摄动理论的相关内容.本文主要运用边界层函数法和空间对照结构理论研究了两类具有Dirichlet边值条件和
政治环境如何影响商业环境对于公共福利至关重要。学术界数十年来一直关注政治与微观经济之间的联系,例如政治关联是否有助于缓解企业的融资约束。但是,一些研究领域仍然较为空白,例如政治关联对企业创新、审计等方面的影响。本文着眼于政治关联与审计质量之间的相互关系,即:政治关联如何影响审计质量?已有文献研究了政治关联与审计质量的关系,但尚未得出一致的结论。此外,已有文献提出的政治关联的资源效应以及资源诅咒效应
实施乡村振兴战略的关键在于培养一支“有文化、懂技术、会经营、善管理”的新型职业农民队伍。职业培训作为高素质新型职业农民队伍建设的基础性工作,效果评价是其必要环节。新型职业农民培训效果评价不仅是政府有效配置资源的参考,也是培训机构优化培训方案的依据,还是提高培训质量的有效途径。为了科学评价新型职业农民培训效果,本研究以江苏为例,综合运用访谈法、问卷法、专家咨询法等质性和量化研究方法,着力解决以下问题
自我关怀是指当个体在面对压力、挫折、失败或自身的缺点时,采用理解接纳、不批判的方式对待自己。随着积极心理学的发展,自我关怀作为一种对待自我的积极健康的态度受到研究者的广泛关注。特别是在青春期,当个体同时面临多种挑战和多样变化时,自我关怀无疑会对青少年的健康发展起着重要的作用。因此,对处于挑战和发展风险中的青少年而言,自我关怀作为一种积极的自我态度的保护性作用值得进一步展开研究。虽然已有关于自我关怀
1949—1955年,这六年是新疆地区和平解放后恢复发展的关键时期,也是新疆地区马克思主义大众化的转型时期。在新民主主义革命时期的基础上,这六年实现了马克思主义在新疆地区由隐蔽转向公开,进而发展为常态化宣传。同时,也是马克思主义在新疆地区的“重新出场”,即不同于新民主主义革命时期的零星、局部式传播,这一时期实现了由点—线—面,进而覆盖到南北疆的全面推进,也与这一时期新疆地区中国共产党组织建设同轨并
这是一个形象主宰话语的时代,这是一个形象制胜的时代;万流归宗,形象制胜。良好的政党形象,在党内能形成强大的整合力、增强党员的认同感和忠诚度;在党外能形成强大的感召力、提升民众的信任感和支持度;在国际上能够提升软实力、增强话语权,为政党和国家谋取利益。形象是政党的无形资产、无价之宝,任何政党若要保持执政地位,都必须具备良好的形象。自中国共产党成立以来,历代领导人无不高度重视党的形象建设。但现实情况是
在区块链系统中,资源受限的轻节点（如移动设备）无法维护全量数据,其需要将查询请求提交到全节点以获取所需数据。由于区块链节点间是互不信任的,全节点在提供查询服务时通常基于默克尔树实现了可验证查询,以使轻节点能够验证所收到的查询结果是否完整。相对于常规查询处理,可验证查询处理除了考虑查询效率,还要考虑查询完整性,兼顾查询效率和查询完整性使得可验证查询处理在功能和性能上受到了诸多制约。首先,资源受限的轻
发展学生的抽象概括能力,形成初步的代数思想,是进一步学习其他数学内容的重要前提。随着代数教与学研究的不断深入,近二十年来,数学教育研究者逐渐达成一个共识:代数思维的发展应该从小学开始,延伸到整个数学教育。这种趋势也同样体现在我国的义务教育课程改革中,例如:2022版《义务教育数学课程标准》明确把“符号意识”作为小学阶段的数学核心素养之一。因此,对我国小学生的早期代数思维进行调查与分析具有重要的理论