若干笛卡尔积图的Tutte多项式研究

作     者：吕江 

作者单位：青海师范大学 

学位级别：硕士

导师姓名：赵海兴

授予年度：2024年

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

主      题：Tutte多项式 棱柱 M(?)bius梯 偏序 笛卡尔积 

摘      要：Tutte引入一个双变量图多项式,是用于分析图与网络属性的重要工具,后来被称为Tutte多项式.Tutte多项式是求解许多图不变量的重要工具,通过对变量赋值或变换可以得到生成树数目、连通生成子图数目、色多项式和可靠多项式等许多图不变量.一般情况下,求解图的Tutte多项式是NP难的,目前,求解出了一些较为规则的图的Tutte多项式,如格子图、扇图、修正Koch图、Apollonian图等. Nathan研究了一些图变换对Tutte多项式的影响,引入了Tutte偏序集,(n,m)-Tutte多项式偏序集(g(n,m),(?))定义在n个点,m条边的图集g(n,m)上,其中G(?)H成立当且仅当T(H,χ,у)-T(G,χ,у)=(χ+у－χу)P(χ,у)成立,其中P(χ,у)是系数非负的多项式,如果P(χ,у)≠0,可以表示为G(?)***偏序集可以体现许多可以由Tutte多项式得到图不变量的一些关系,比如Tutte偏序集中的最大图,它的可靠多项式也最大.可以借助Tutte偏序集来探索图之间的一些关系,探究图结构对图的Tutte多项式产生的影响. 棱柱是几何学上著名的图,是3正则图,也是圈和2个点的完全图的笛卡尔积;M(?)bius梯和棱柱结构相似.本文研究了棱柱和M(?)bius梯的Tutte多项式以及一些笛卡尔积图集上的性质. 本文基于Tutte多项式的删除-收缩定义计算了各种图的Tutte多项式,结合分裂公式和图变换研究各个图集中图的Tutte多项式之间的关系.主要研究结果如下: 1.得到了棱柱和M(?)bius梯的Tutte多项式的递推公式,并且给出了计算棱柱的Tutte多项式的Maple程序. 2.确定了基于Tutte偏序集定义,梯图为树和P2的笛卡尔积图集的中的最大图,星图和P2的笛卡尔积为最小图,固定直径的树与P2的笛卡尔积图集中的最小结构. 3.确定了基于Tutte偏序集定义,棱柱为单圈图和P2的笛卡尔积图集中的最大图,星图和3圈的一个单点连接和P2的笛卡尔积为最小图,圈直径不同单圈图和P2的笛卡尔积之间的部分关系.