编辑推荐:
对于连通图,三个顶点的Fermat差值定义为它们到某一公共顶点的距离之和的最小值减去它们两两距离之和的一半。本文研究了给定阶数和圈长的单圈图的平均Fermat差值。通过建立投影恒等式,研究人员将问题约化为唯一圈上的加权三次型。研究人员获得了圈的精确公式,并建立
对于连通图,三个顶点的Fermat差值定义为它们到某一公共顶点的距离之和的最小值减去它们两两距离之和的一半。本文研究了给定阶数和圈长的单圈图的平均Fermat差值。通过建立投影恒等式,研究人员将问题约化为唯一圈上的加权三次型。研究人员获得了圈的精确公式,并建立了一个紧下界以及所有达到等号的极值图的刻画。研究人员进一步推导了给定阶数和圈长的单圈图的一般上界。最后,研究人员确定了固定阶数的所有单圈图中平均Fermat差值的最大值,并刻画了相应的极值图。
本研究聚焦于单圈图(unicyclic graphs)上平均Fermat差值(average Fermat difference)的极值问题。基于距离的图不变量(distance-based graph invariants)在图结构与网络拓扑研究中具有基础性地位,其中最短路径距离(geodesic distance)是连通性最基本的度量之一。Wiener指数(Wiener index)由Wiener在分子结构与物理性质研究中引入,其后成为化学图论与极值图论的重要研究对象,其归一化形式即平均测地距离,在网络科学尤其是小世界现象(small-world phenomenon)的刻画中发挥核心作用。图距离的自然推广是考虑多于两个顶点之间的距离,Chartrand等人引入了Steiner距离(Steiner distance)的概念,Dankelmann等人随后研究了平均Steiner距离并建立了基本界,Li等人引入了Steiner k-Wiener指数以推广经典Wiener指数。三顶点距离的另一自然进路源自经典Fermat–Torricelli问题,即在图中寻找使到三个给定顶点距离之和最小的点,这与中位数及网络选址问题密切相关。对于三个终端,Fermat距离与Steiner距离重合,因而平均Fermat距离与Steiner–Wiener指数理论紧密关联。由三角不等式可得三点Fermat距离与普通两两距离之间的关系,两者之差即Fermat差值。Peng等人在复杂网络背景下明确研究了Fermat差值统计量及其拓扑意义。对于n阶连通图G,平均Fermat差值的定义蕴含其与Wiener指数和Steiner 3-Wiener指数之间的直接联系。Kov?e等人建立了后两个指数之间的相应不等式并以模图(modular graph)刻画了等号情形,因此Fermat差值衡量了三顶点距离未能 admit 公共最短路径分解的程度,其极值行为取决于这两个距离指数之间的相互作用而非任一指数单独的性质。单圈图由唯一圈及附着于其各顶点的树构成,这一结构使得研究人员能够将循环贡献与附着树分离,同时保留三顶点距离的本质特征。此前已有研究考察了复杂网络中的Fermat差值统计量以及单圈图上Wiener指数和Steiner k-Wiener指数等极值距离指数,但这些结果不能直接确定给定阶数和圈长的单圈图平均Fermat差值的极值行为。为此,研究人员发展了投影方法,将平均Fermat差值约化为唯一圈上的加权三次表达式,从而得以研究三个相关问题:圈的精确求值、给定阶数和圈长下的最小平均Fermat差值及其等号情形、以及相同约束下的上界,并进一步确定了给定阶数所有单圈图中平均Fermat差值的最大值并刻画了相应极值图。
在关键技术方法方面,研究人员主要采用了以下手段:建立投影恒等式(projection identity),将单圈图上任意顶点三元组的Fermat差值约化为其投影在唯一圈上的加权三次型;利用组合计数与容斥原理推导圈上Fermat差值总和的精确公式;通过展开加权三次表达式并分析二次项与三次项系数的非负性建立紧下界;借助随机弧分割与分离概率估计、以及竞赛图(tournament)中有向三角形数量的上界(Lemma 4)来推导上界;并对小阶数情形逐一计算上界以完成极值图的验证。研究未涉及特定样本队列来源。
研究结果方面,首先,关于m-圈上的Fermat差值,定理1给出:设x、y、z为m-圈上互异顶点,将圈切成三段长度分别为a、b、c,令h = ?m/2?,则当max{a,b,c} < h时Fermat差值非零,否则为零,并给出了相应的Fermat距离表达式;推论1给出总Fermat差值的计算。引理1通过对有序正整数三元组的计数与容斥得到组合恒等式(1)。定理2给出了m-圈上Fermat差值总和的精确公式(2),并列出闭形式表格,进而得到m → ∞时的渐近公式。其次,关于单圈图上的投影,定理3证明:对任意顶点三元组,其Fermat差值等于其投影在圈上的Fermat差值,且当两个顶点共享同一投影时Fermat差值为零;定理4据此给出单圈图总Fermat差值的加权圈表达式(3)。第三,关于紧下界,定理5证明固定m时平均Fermat差值的下界是紧的且可由至多一个非平凡根树实现;推论2给出n ≥ 4m时下界为零且最小值当且仅当特定条件成立;定理6完整刻画了到达下界的充要条件,分m为奇数、m为偶数且特定取值、以及m=4等情形讨论,指出m=4的单圈图是模图。第四,关于上界,引理2给出加权量的逐点上界(5),引理3通过随机弧分割与分离概率证明了三根分离概率的期望上界,引理4证明t个顶点的竞赛图中有向3-圈数量至多为特定值,引理5利用竞赛图构造证明三次项的上界,引理6给出三根属于三条不同弧的概率上界(7);定理7综合上述引理得到给定阶数和圈长下单圈图平均Fermat差值的上界,并指出该上界可能不紧。最后,定理8确定了给定n个顶点的单圈图平均Fermat差值的全局极值:构造由圈加一条悬挂边得到的图,给出公式(8),并证明在第一种情形下该图为唯一最大化图,在第二种情形下除n=6时三角形各根带一叶、n=8时五边形三个根(间隙为1,2,2)各带一叶两个额外情形外唯一。
讨论部分总结了全文:研究人员通过将问题约化为加权圈,获得了圈的精确公式,建立了带有极值图刻画的紧下界,推导了给定阶数和圈长的上界,并确定了固定阶数所有单圈图中的紧上界,这些结果揭示了圈长与附着树分布对平均Fermat差值的作用。研究结论为:确定每个给定圈长的精确上界以及将这些结果推广到双圈图和更一般图类仍是有趣的待研究问题。