图的Kirchhoff指标的研究进展

打开文本图片集

摘 要：图论在矩阵论、组合数学、组合优化、运筹学、线性规划、电子学以及通讯和计算机科学等诸多方面都有广泛应用。连通图G两个顶点vi和vj之间的电阻距离rij定义为：用单位电阻来代替G中的每条边构造出的电网络N中节点i和j之间的等效电阻的阻值。Klein和Randi"[1]把Kirchhoff指标Kf（G）定义为G中所有点对之间的电阻距离之和。在很多领域，Kirchhoff指标有着广泛应用，并且广为研究。本文我们主要介绍连通图的Kirchhoff指标的研究进展。

关键词：图论；连通图；Kirchhoff指标；研究进展

图论起源于著名的哥尼斯堡七桥问题。19世纪末期，图论应用于电网络方程组和有机化学中的分子机构。20世纪中叶，由于计算机的发展，图论用来求解生产管理、军事、交通运输、计算机和网络通信等领域中的离散问题，现在图论在物理学、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学、管理科学等应用领域均有应用。

图论中的图G是指有序三元组（V（G），E（G），Ψ），其中V（G）代表图的非空顶点集，其中的元素称为顶点，E（G）代表的是图的边集，其中的元素称为边，Ψ称为关联函数，表示的是E（G）到G中无序顶点对的一个映射。假如e是某一条边，其中顶点u，v满足等式Ψ（e）=uv，则称e是连接两个顶点的边，并称这两个顶点是e的端点，也称这条边e和它两个端点u，v是相关联的。一个不含环和多重边的图我们称之为简单图。如果G中每一对不同的顶点u，v都有路相连，则称G是联通的。否则，就称G是不连通的。设图G是一个简单连通图，顶点集为{v1，v2，…vn}。如果G中的每条边用单位电阻代替，则相应构造出了一个电网络N。而顶点vi和vj之间的电阻距离（Resistance distance）被定义为N中节点vi和vj之间的有效电阻的阻值，记作rij。

Klein和Randic"把Kirchhoff指标（Kirchhoff index）定义为G中所有点对之间的电阻距离之和，记为Kf（G），即

例如，计算下图G，如图1（1）所示，电阻距离和Kirchhoff指标，用单位电阻来代替每条边得到相应的电网络，如图1（2）所示。

根据欧姆定律，

则由Kirchhoff指标的定义，我们可以得到：

虽然对任意的图G，己经得到了电阻距离和Kirchhoff指标的通用计算公式，但是这些公式计算量非常大，计算图的Kirchhoff指标从算法上很难实现。因此，对于一些特殊图类，人们尝试着去给出一些简单的计算公式。到目前为止，很多特殊图类给出了结果。现在已经得到解决的图类主要有：

（1）完全图Kn[2]

（2）圈Cn[2]

（3）完全二部图Km，n[3]

位于顶点数为m（或n）的色类中的任意两个顶点间的电阻距离是 （或 ），位于不同的色类中的任意两点的电阻距离为

有些图类虽然很难给出计算公式，但是我们可以退一步去估计这类图的Kirchhoff指标的界，找到这类图的Kirchhoff指标的变化范围，并且进一步刻画达到界的极值图。这方面也有了一些初步的结论。

定理1[4]对n个顶点的连通图G，

第一个等号成立当且仅当G=Kn，第二个等号成立当且仅当G=Pn。

定理2[5]

等号成立当且仅当G=Kn或G=Sn。

定理3[5]设v是G的匹配数，则

（1）若 ，则 ，等号成立当且仅当 G=Kn。

（2）若 ，则

等号成立当且仅当

Das在2010年对上述结论进行改进，找到了更低的下界。

定理4设G是有n个顶点m条边的连通图（n>2），其最大度为Δ，第二个最大度为Δ2最小度为δ，则

等式成立当且仅当G=K1，n-1，或者G=Kn。

定理5设G（≠Kn）是有n个顶点m条边的连通图（n>2），其最大度为Δ，最小度为δ，则

等式成立当且仅当G=K1，n-1或者G=Kin，n-1或者G=Kn-e。

这里Kin，n-1是指将完全图Kw的一个顶点和路Pn-w的一个端点通过增加一条边连接在一起得到的图形。

2013年Li改进了Das的结论，找到了一个更低的Kirchhoff指标的下界。

定理6设G是有n个顶点m条边的连通图（n≥2）。

等号成立当且仅当G为 或者

这里Kn-e定义为从Kn中删除一条边e所得到的图，Sn+e定义为从Sn中增加一条边所得到的图。

2013年Deng研究了二部图的补图的Kirchhoff指标的极值，他将二部图的补图的Kirchhoff指标与G中闭路的条数联系在一起，得到以下结论：

定理7设G是具有n个顶点m条边的二部图（n≥2），则

这里S（G）图G的细分，即在G的每条边上插入一个新的顶点所得到的图形。

Tr（A2kS（G）））指S（G）中长度为2k的闭途径的数目。该定理表示，对于任意两个二部图G1和G2，比较 和 可以转化为比较Tr（A2kS（G）））进而转化为比较S（G1）和S（G2）中闭途径的数目。所以该定理提供了一个求二部图的补图的Kirchhoff指标的一个很好的方法。

以上总结了Kirchhoff指标的研究现状，对于更多的Kirchhoff指标的文章，读者可以查阅先关文献。

[参考文献]

[1]D.J.Klein and M.Randi，Resistance distance，J.Math.Chem.12（1993）81-95.

[2]I.Lukovits，S.Nikolic and N.Trinajstic，Resistance distance in regular graphs，Int.J.Quantum.Chem.71（1999）217-225.

[3]B.H.McRae，B.G.Dicksonl，T.H.Keitt and V.B.Shah，Using circuit theory to model connectivity in ecology，evolution and conservation，Ecology 89（2008）2712-2724.

[4]J.L.Palacios，Resistance distance in graphs and random walks，Int.J.Quantum Chem.81（200l）29-33.

[5]B.Zhou and N.Trinajsti，A note on Kirchhoff index，Chem.Phys.Lett.455（l-3）（2008）120-130.

推荐访问:研究进展 指标 Kirchhoff