图的电阻距离的一个下界可达性

连通图中任意2个顶点之间的电阻距离定义为将图中每条边用单位电阻代替后所得电网络中这2个节点之间的有效电阻.应用Rayleigh单调性法则等电网络理论以及网孔分析法,本文刻画了图的电阻距离的一个下界可达的充要条件.     

合成图的Laplacian特征值

给出了任意两个图的合成图的Ｌａｐｌａｃｉａｎ特征值和特征向量,同时得出了合成图的生成树的数目。     

树的Laplacian矩阵的第二大特征值

设T是n阶树，记μ2(T)为树T的Laplacian矩阵的第二大特征值，本文给出仅依赖阶数的树的Laplacian矩阵的第二大特征值的界，即证明了1≤ μ2(T)≤√(n-1)^2-4/4 1左边等号成立当且仅当T≌K1,n-1。     

用秩1矩阵矫正法计算两类图的生成树数

设P是完全二部图K_m,n的一个匹配,本文用秩1矩阵矫正法给出了完全二部图K_m,n中包含P中的所有边和不包含P中边的生成树数目公式的一个简单证明.     

距离图的点荫度

实数距离图G(R，D)是顶点集为实数轴上的所有点，顶点u,v∈R相邻当且仅当|u-v|∈D，其中D是一个正实数集．讨论了当D为1到δ的区间时，实数距离图G(R，D)的点荫度．特别地，当3D是某正整数集合，Z是整数集时，得出了整数距离图G(Z，D)的点荫度的几个上界．     

两个图的Laplacian谱距离

把两个图的邻接谱距离推广到两个图的Laplacian谱距离,给出了任意两个图的Laplacian谱距离的一般性结果,最后计算出了一些特殊图的Laplacian谱距离。     

图的电阻指数的单调性质

首先利用图的结构给出了一个计算图的电阻指数的公式.然后通过图变换给出了图的电阻指数的3个单调性质,并进行了证明.     

图的距离Estrada指数

设G是一个n阶连通图,G的距离特征值为γ1≥γ2≥…≥γn,定义图G的距离Estrada指数如下:DEE(G)=∑neγi.该文研究图的距离Estrada指数的性质,并给出了DEE的一些界.     

计算超立方体图电阻距离和Kirchhoff指标的新方法

连通(分子)图G的两个顶点i和j之间的电阻距离为通过用单位电阻来代替G中的每条边而相应构造出的电网络中结点i和j之间的有效电阻。Kirchhoff指标Kf(G)是G中所有的顶点对的电阻距离之和。本文提出一种新的简单方法,利用距离传递性给出了超立方体图的电阻距离和Kirchhoff指标的计算公式。     

关于图的平均距离的一点注

本文证明,若图G是树或者是Hamilton通图,则Ivd(G)≥D(G).     

图论中结点距离

文章分析了无向图中结点的距离与图的连通性、图的邻接矩阵之间的关系,并且给出了求两个结点距离的一种方法 .     

图结构上下文及在图聚类中的应用

图结构特征的提取以及距离度量是计算机视觉和模式识别中的重要内容。针对传统的图上下文描述子中只考虑每个柱形区域内的特征点数目而忽略特征点之间的结构信息的问题,提出一种图的结构上下文描述子及距离度量方法。首先对图的所有顶点建立图结构上下文描述子;其次,利用二次卡方（QC）距离方法实现图的距离度量;最后,采用最小生成树聚类算法实现图聚类。实验表明,该方法对于一些非刚性变换的图聚类有较好的效果。     

连通图的平均距离

图的直径是图中两点距离的最大值,图G的平均距离,记作D(G),它是图的任两点距离的平均值。在网络分析中,图的直径和平均距离是重要的示性数。该文对某些较简单的图类:简单圈、树等的平均距离进行估算,证明了若G是直径不超过3的n阶连通图,则它的平均距离至多是n/δ+1,这里δ是G的最小度。最后,对n阶连通图的平均距离的上界提出了一个猜测     

图在路由选择中的应用

介绍了广播路由选择方式中的生成树算法 ,提出了用图的广度遍历算法来实现生成树的思想     

图生成树棵数的一种求法

本文提出了对给定图 G来说 ,计算它的所有的生成树棵数的一种方法 ,即由 Cayley定理与 Binet-Cauchy定理来推导一个公式τ(G) =det(KKT) ,为了证明此公式的成立 ,还证明了从一个图的完全关联矩阵 M(G)中删去任意一行后 ,得到的矩阵 K和 K的转置 KT满足 Binet-Cauchy条件。公式τ(G) =det(KKT)的证明是由一个图的生成树的棵数公式τ(G) =τ(G -e) τ(G . e)与具有以上性质的矩阵 K与 KT且 det(KKT) =∑ Ki Ki=∑K2i 合起来证明。     

平面格图生成树的计数

设ｔ（ｍ,ｎ）和ｔ（ｍ,ｎ）分别是平面ｍ×ｎ格图生成树和对称生成树的数目,从而给出了ｔ（３,ｎ）和ｔ（３,ｎ）的闭公式以及ｔ（ｍ,ｎ）递推式阶的估计．     

完全二分图的生成树的个数

给出了生成子图的定义．证明了生成子图的构造定理和计数定理．提出了任意G（p,q）的生成树的计数方法和构造方法．介绍了完全二分图K3,3的生成树的计数和构造．     

循环图及其补图的拉普拉斯矩阵的谱

文章利用循环矩阵的性质,获得循环图G(n;±S)=(V,E)的特征值λr=sum from j=1 to n ajω(j-1)r,r=0,1,…,n-1。其中ω=cos2π/n+isin2π/n。并且循环图及其补图的拉普拉斯矩阵的谱sum from j=1 to n aj-sum from j=1 to n ajω(j-1)r,n-sum from j=1 to n ajω(j-1)r。     

动态图上的最短路径距离并行算法

设计动态图上最短路径距离查询的并行计算框架。通过构建增量图的方法,实现一个批次内的多个查询在不同数据图版本的多线程并发执行。对于每个查询,使用双向宽度优先搜索算法来减少搜索空间,并提出搜索过程中扩展方向的决策函数。利用BSR对数据图邻接表进行编码,结合SIMD指令和图顶点重标号算法,进一步提升数据级并行度。在真实图数据集下的大量实验验证了所提方法的高效性。     

关于图的代数连通度的注记

n阶连通图G的代数连通度、点连通度和边连通度分别记作α(G) ,κ(G)和λ(G) .本文给出了当 2 κ(G) n- 2时 ,α(G) =κ(G)成立的充要条件 ,讨论了α(G)的代数重数以及相应于特征值α(G)的特征向量的性质 .最后给出了当 1 λ(G) n- 2时 ,α(G) =λ(G)的充要条件 .