仿高阶矩的结点不变量及其组成的图不变量

借鉴高阶矩的方法,采用层序的计算框架,依据结点的连接距离和层序信息定义了20种结点不变量。这些结点不变量体现图整体的上下偏分布特性、整体不均匀性和整体平滑性,结点不变量中的每层结点度数平方之和反映了层内结点度数的分布情况。通过比较这些结点不变量的可区分结点数,发现每层结点度数平方之和明显改善了结点不变量的细分能力。把排序后的结点不变量组成一个矢量后作为图的不变量。计算结果表明,共有9种图不变量可以区分所有结点数N<25的非同构树和N<34的非同构同胚不可约树(没有度数为2的树),对于更多结点的树,还没有发现非同构树有相同图不变量的例子;把这些图不变量应用到非同构图(N<10),区分结果好于文献[8]中列出的22种图不变量的19种,而且文中9种图不变量的简并度不大,提高了随机图的同构测试性能。

基于层序遍历的顶点不变量及其图不变量

为了寻找更好性能的图不变量,利用层序遍历过程中的顶点数据经加权累加定义了15种顶点不变量,每一种顶点不变量排序后可以组成一种图不变量。层序遍历时将顶点度数分为同层度数、向前度数和向后度数,其中同层度数和向后度数包含回路数信息。依据对顶点的细分能力,挑选出3种顶点不变量,组成图不变量,其不同组合对于各种非同构连通图具有较好的区分性能,不仅对图顶点数N≤8的非同构图全部可以区分,而且将N=9的不可区分图数量从文献[9]的989种降到40种,且其简并度将趋近2,随机测试表明这些图不变量具有很好的区分度。

图的多项式不变量的一个推广

图论中的一个核心问题是研究图的不变量.对于给定的一个平图,可以建立该图的Tutte多项式不变量.一直以来,认为Tutte多项式是最一般的图的不变量.经典的Tutte多项式不变量是含有2个变元x,y的多项式,但是这个多项式却不能区分所有的图.这促使我们考虑可以通过增加变元的方法来细分图的类别.对于给定一个的平图,将图的Tutte多项式不变量进行了推广,得到一个新的n变元多项式,并证明其是图的不变量.进而,也验证它能区分Tutte多项式不能区分的一类图,这类图是给定的一个图与在这个图上再加一些与之不相交的点.

与图的支配性有关的不变量的若干不等式

证明了关于图的支配数、上支配数、全支配数、连通支配数、点－边弱（强）支配数及边－点弱（强）支配数的一些不等式。

与图的两个支撑子图簇有关的介值性质

设Ｔ和Ｔ＇为简单图。若存在边ｅ∈Ｔ－Ｔ＇及ｅ＇∈Ｔ＇－Ｔ使Ｔ＇＝Ｔ－ｅ＋ｅ＇，则称Ｔ→Ｔ＇为简单边变换（ＳＥＥ）．对图的整值不变量，如果Ｔ→Ｔ＇为ＳＥＥ蕴涵则称对ＳＥＥ连续。对ｍ个分支、ｐ个顶点、ｑ条边的图Ｇ，以Ｃ＿ｎ（Ｇ）记６的恰有ｍ个分支ｎ条边的支撑于图簇（ｐ－ｍ≤ｎ≤ｑ）．记Ｃ＿ｎ（Ｇ）为Ｇ的具有ｎ条边的支撑子图簇（１≤ｎ≤ｑ）．证明了：ａ．若对ＳＥＥ连续，则对任意满足的Ｔ，Ｔ＇∈Ｃ＿ｎ（Ｇ）及整数ｋ，至少存在（ｎ＋ｍ＋２－ｐ）（ｑ－ｎ）Ｔ＂∈Ｃ＿ｎ（Ｇ）使．对任意Ｔ，Ｔ＇∈Ｃ＿ｎ（Ｇ）及ｋ，至少存在ｎ（ｑ－ｎ）个Ｔ＂∈Ｃ＿ｎ（Ｇ）使．给出了ａ和ｂ这两个结果的对偶定理。

基于极小T-不变量增加的Petri网可达性分析

基于极小T-不变量增加的Petri网的可达性分析,首先对网的状态方程加以合理的约束,求得一组特征解向量;然后利用扩展极小T-不变量关系图和扩展借矩阵在这些特征解向量的基础上适当添加整数倍的极小T-不变量;最后再判断这个添加极小T-不变量后的解向量的可达性。该方法不仅能判定一类含T-不变量Petri网的可达性,而且能在可达的情况下求得一个合法的变迁发生序列,并在一定程度上简化了可达性分析的过程。

图的几个介值性质

证明图的若干不变量相对于任一简单图的子树的簇具有介值性。