图的符号逆和生成树计数

作     者：马哓旭 

作者单位：烟台大学 

学位级别：硕士

导师姓名：杨玉军

授予年度：2024年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：符号可逆图 生成树 完美匹配 六角链 Kirchhoff矩阵-树定理 

摘      要：设G是简单图,如果给G的每条边都标一个符号(正号或负号),所得的图称为符号图.给定一个简单图G,如果它的邻接矩阵可逆,并且是某个符号图的邻接矩阵,则称G是符号可逆图.图的生成树是包含图的所有顶点的无圈连通子图.图的完美匹配是一组不相交的边的集合,且这些边覆盖了图的所有顶点.本文主要研究一个图是符号可逆图的充要条件以及特殊的六角链和四六角链中包含完美匹配的生成树的计数.本文共五章,具体内容如下: 第1章,介绍本文所用到的基本概念、术语和记号,以及图的符号逆和生成树计数的研究背景和研究进展. 第2章,我们得到了一类图是符号可逆的充要条件,并根据其邻接矩阵的逆矩阵构造出了这类图的符号可逆图. 第3章,我们计算了具有唯一转向六边形的六角链中包含完美匹配的生成树数目,给出了其解析表达式. 第4章,我们给出了一类四六角链图中包含完美匹配的生成树数目的精确的解析表达式. 最后,在第5章中,我们总结了本文的主要研究内容,并提出了后续的研究问题.