特殊图类的独立集与匹配计数问题

发布时间：2024-06-13 20:16

　　图G的独立集计数指标(简称M-S指标)是指G中所有独立集的数目.图G的匹配计数指标(简称H指标)是指G中所有匹配的数目.M-S指标和H指标是结构化学中非常重要的两个拓扑指标.这两个拓扑指标的研究主要包括计数问题与排序问题.图结构的构造是研究这些指标的重要工具,常用的方法有两种:一是由若干个图通过特定连接方式进行连接,得到的图称为连接图;二是由一些图通过图的结构运算而产生,得到的图称为运算图.本文主要研究特殊的拷贝连接图与运算图的独立集与匹配计数及排序问题,主要工作包括以下三部分.(i)受六角系统、圈连接图等图类的顶点连接方式以及计算机互连网络构造方法的启发,利用图拷贝的特殊连接方式定义了四类特殊的拷贝连接图Qmi(n,k),Pm,s,t r,j(Cm,s,t r,j(n,k),Tr(m1,m2,m3),其中i=1,2,3,4,j=1,2,3.(ii)研究了拷贝连接图Qmi(n,k),i=1,2,3,4,和特殊图的冠积与边冠积的独立集与匹配计数问题,并得到了对应的计数表达式.其中,关于冠积和边冠积的独立集与匹配计数问题是将已有文献中的一些研究成果进行拓展.(iii)对k=1,2,…,r,...

【文章页数】：86 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 引言
第2章 拷贝连接图与两类运算图
    2.1 拷贝连接图
    2.2 图的冠积G○H与边冠积G◇H
第3章 独立集与匹配计数
    3.1 相关概念及引理
    3.2 独立集计数
        3.2.1 拷贝连接图Qm
i(n,k)的独立集计数
        3.2.2 特殊图的冠积与边冠积的独立集计数
    3.3 匹配计数
        3.3.1 拷贝连接图Qm
i(n,k)的匹配计数
        3.3.2 特殊图的冠积的匹配计数
第4章 独立集与匹配计数指标的排序
    4.1 相关概念及引理
    4.2 独立集计数指标的排序
        4.2.1 拷贝连接图Pm,s,t
r,j(n,k)关于独立集计数指标的排序
        4.2.2 拷贝连接图Cm,s,t
r,j(n,k)关于独立集计数指标的排序
    4.3 匹配计数指标的排序
        4.3.1 拷贝连接图Pm,s,t
r,j(n,k)关于匹配计数指标的排序
        4.3.2 拷贝连接图Cm,s,t
r,j(n,k)关于匹配指标的排序
    4.4 拷贝连接图Tr(m₁,m₂,m₃)关于匹配能量的排序
第5章 结束语
参考文献
附录
致谢



本文编号：3993596

suoshi