棱柱是圈Cn和路P2 的笛卡尔积,也可以看作两端连接的梯图.Möbius梯的结构与棱柱相似,可看作扭曲后两端连接的梯图,并且自然地嵌入Möb ius带.图的Tutte多项式是一个双变量多项式图不变量,通过对变量赋值或变换可以得到生成树数目、连通生成子图数目、色多项式和可靠多项式等许多图不变量.本文运用 Tutte多项式的删除-收缩运算,获得了棱柱和Möb ius 梯的Tutte多项式.
Abstract
A prism is a cartesian product of the cycle and the path can also be seen as a ladder graph connected at both ends.The structure of a Möbius ladder is similar to that of a prism,and can be seen as a twisted ladder graph connected at both ends,naturally embedded with straps.The Tutte polynomial of a graph is a bivariate polynomial graph invariant.By assigning or transforming variables,many graph invari-ants can be obtained,such as the number of spanning trees,the number of connected spanning subgraphs,chromatic polynomials,and reliability polynomials.This article uses the deletion-contraction operation of the Tutte polynomial to obtain the Tutte polynomials for prisms and Möbius ladders.
万方数据