乘积图和F-Sum图的Steiner K-距离

图的距离是图论中非常重要且基本的概念,是研究基于距离的图不变量的基础。Steiner距离是图论组合研究中的经典问题。本文运用Steiner树的定义证明了corona积的Steiner k-半径和cluster积的Steiner k-半径的上下界以及F-sum图的Steiner距离和Steiner k-直径的界。

单圈图的Steiner k-general Wiener指数

对于连通图G,当3≤k≤n-2时,图G的Steiner k-general Wiener指数定义为SW_(k)^(m)(G)=∑S■V(G)|S|=kd^(m)(S),(m≥1),其中d(S)表示点集S的Steiner距离,即图G中包含点集S的最小连通子树的边数.给出了单圈图的SW_(k)^(m)(G)下界,并得到对应的极图.

求解绝对值距离Steiner最小树的改进元胞蚂蚁算法

绝对值距离Steiner最小树问题是在集成电路布线等领域应用广泛的属于NP难的经典组合优化问题,由于该问题的搜索空间与元胞自动机的结构相似,设计了求解绝对值距离Steiner最小树问题的改进的元胞蚂蚁算法。经大量数据实验表明,该算法要比最小生成树平均改进15%,优于多数已有的基于最小生成树的近似算法,验证了算法的实用性。

单圈图的Steiner Wiener指数的极值问题

Wiener指数作为化学图论中的一个重要的化学指标,是连通图的任意两个顶点的距离之和。Steiner Wiener指数是Wiener指数的一种推广形式,定义为所有k个顶点的集合S的Steiner距离的和,其中S的Steiner距离是包含S的最小连通子图的边数。本文研究了具有最小(大)Steiner Wiener指数的单圈图结构。

圈C_(n)的Steiner 3-Wiener指标

令图G是一个连通图,图G的点集是V(G),边集是E(G).当2≤k≤n-1时,图G的Steiner_(k)-Wiener指标定义为SW_(k)(G)=∑S■V(G),|S|=k d_(G)(S),其中d G(S)表示图G中S的Steiner距离,即连通图G中包含点集S的最小连通子图的边数.本文利用Steiner k-Hosoya多项式给出了圈C_(n)的Steiner 3-Wiener指标的表达式.

绝对值距离Steiner最小树问题的二进制粒子群算法

绝对值距离Steiner最小树问题是在铺设网络线缆等领域应用广泛的一个NP难的经典组合优化问题。针对此问题,提出基于最小生成树问题的二进制粒子群算法。该算法首先对网络节点进行编码,计算适应度函数值,并使用二进制粒子群算法求解Steiner点。数据实验结果表明,该算法具有实用性。

圈C_n的k-Steiner Wiener指数和超k-Steiner Wiener指数

点集S的Steiner距离d(S)是指包含子集S的最小连通子图的边数即d(S)=min{|E(H)|:S■V(H),H是G的连通子图}.2016年,李学良,毛亚平和Gutman提出了k-Steiner Wiener指数SW k(G)和超k-Steiner Wiener指数SWW k(G)的概念,SW k(G)=∑S■V(G),|S|=k d(S)SWWk(G)=1/2∑S■V(G),|S|=k d(S)+1/2∑S■V(G),|S|=k d(S)2.文章利用k-Hosoya多项式给出了圈C n的k-Steiner Wiener指数和超k-Steiner Wiener指数.

完全二部图的超k-Steiner Wiener指数

文章利用Hosoya多项式和组合恒等式给出了完全二部图Km,n的超k-Steiner Wiener指数的计算公式.

给定匹配数的Steiner Wiener指数极小树

本文讨论了给定匹配数的树中k-Steiner Wiener指数的极小值,并刻画了极图。图G的k-Steiner Wiener指数定义为图G中任意k-点集S的Steiner距离d(S)的和,而点集S的Steiner距离d(S) 是包含点集S的最小子树的边的数目。

单圈图的Steiner (n-1)-Wiener指标

令G是一个连通图.当2≤k≤n-1时,图G的Steiner k-Wiener指标表示V(G)中所有k子集S的Steiner距离之和.如果一个连通图具有相同的顶点数和边数,则称为单圈图.通过对单圈图做变换,给出了单圈图Steiner (n-1)-Wiener指标的计算式,确定了单圈图Steiner (n-1)-Wiener指标的上、下界,并刻画了达到上、下界时的极图.