Two Problems Related To The Enumeration Of Spanning Trees

In this paper,we study the relationship between the determinant of an alternating link and the number of the spanning trees of its Tait graph,and the enumeration of the spanning trees of Middle graphs.The paper consists of three chapters.In the first chapter,we mainly introduce some basic concepts in graph theory and knot theory,as well as the research background on spanning trees.In the second chapter,we will give two simpler methods to prove the known relationship between the determinant of an alternating link and the number of the spanning trees of its Tait graph.First,we prove by using the skein relation satisfied by the determinant of an alternating link and mathematical induction;Then,we prove by observing the one-to-one correspondence between the diagram of an alternating link and the directed Medial graph of its Tait graph.In the third chapter,firstly,a new proof is given for the weighted spanning tree enumerator of the Middle graph of the weighted graph by using the generalized WyeDelta transformation and electrically equivalent principle of substitution;Next,the definition of the weighted Middle graph of the directed weighted graph G is given,and the relationship between the vertex weighted complexity of the weighted Middle graph and the edge weighted complexity of the original graph is obtained.When the weight of each edge and each vertex of G is 1,the spanning tree enumeration formula of the Middle graph of the general directed graph is obtained.