2023年7月19日发(作者：)

维普资讯

第２３卷第６期　２００７年６月　甘肃科技　Ｇａｎ￣ｕ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　Ｖｒ０Ｚ．２３　Ｎｏ．６　Ｊｕｎ．　２００７　欧拉回路与生成树的关系　卢鹏丽　（兰州理工大学计算机与通信学院，甘肃兰州７３００５０）　摘要：计算图（有向图或无向图）中生成树的个数可以用组合的方法，也可以用代数的方法。介绍　了用代数的方法求图中生成树的个数，给出了欧拉回路与生成树的关系，并将其应用于实际的问题　中，解决了一类等价类问题。　关键词：矩阵树定理；欧拉图；生成树；邮递员问题；二进制ｄｅ　Ｂｒｕｉｊｎ序列　中图分类号：Ｏ１．１５　式的值啪。例如图２，ｋｉｒｅｈｈｏｆｆ矩阵为　１代数方法求图中生成树的个数　】．１矩阵树定理计算无向图中生成树的个数　矩阵树定理是１８４７年由ｋｉｒｅｈｈｏｆｆ提出的，主　要用于电路计算。但是对于计算生成树的个数同样　有用。　对于一个无向图Ｇ＝（Ｖ，Ｅ），Ｖ一（ｖｌ，ｖ２，　１　—１　０　０　—　１　　２　—１　一　ｌ　Ｈ：＝　，Ｈ中ｈ　的　０　０　２　０　０　０　ｖ…．．，ｖ　），Ａ为其邻接矩阵。点ｖ　的度为ｄ　（１４　ｉ≤ｎ），矩阵Ｂ＝ｄｉａｇ（ｄ　，ｄｚ，…，ｄ　）称为图Ｇ的　度矩阵。则定义ｋｉｒｅｈｈｏｆｆ矩阵Ｈ＝Ｂ—Ａ。　代数余子式为　０　—１　２　０　一　１　　０　０　—　１　０　０　０　２　０　—１　—１　ｌ　０　—ｌ　２　一４，所以，图Ｄ　０　—１　ｌ　矩阵树定理为：图Ｇ的生成树的个数等于Ｈ的　任意一个代数余子式的值［１］。其中Ｈ的以（　）为　人口元素的代数余子式的值为去掉ｉ行和ｊ列元素　的行列式值再乘以（一１）。＋ｊ。例如图１，ｋｉｒｅｈｈｏｆｆ矩　阵Ｈ如下。　４　—１　——的以顶点ｌ为根的生成树的个数为４。　０　０　一　一　２　ｌ２　　５　８　９　４　　１　—１　Ｏ　一１７　５　１　３　—Ｏ　Ｏ　—１　—１　—６　１　Ｏ　１　Ｏ　Ｏ　一１　——３　—１　１　３　一１　Ｏ　１　Ｏ　一图２有向图　图３　３×３的网格　１　—１　４　—１　一ｌ　一１　Ｏ　Ｏ　—１　３　２　欧拉回路与生成树的关系　２．１欧拉回路　圈１无向图　Ｈ的所有代数余子式的值为１２８，所以，图Ｇ的生　成树的个数为１２８。　１．２有向图（或多重图）中生成树的计数　有向图Ｄ＝（Ｖ，Ｅ），Ｖ一｛ｖｌ，ｖ２，ｖ３，…，ｖ　），顶　欧拉图是欧拉在１７３６年为解决著名的Ｋｏｎｇｓ—　ｂｅｒｇ七桥难题提出来的。　对于一个图Ｇ，包含Ｇ的每条边的简单回路称　为欧拉回路。具有欧拉回路的图称为欧拉图。简单　地讲，若图Ｇ为一个欧拉图，则能够不重复地一笔　画出来。　２．２平衡图中欧拉回路与生成树的关系　对于一个有向图Ｄ，若所有顶点的入度都等手　点的入度为ｉｎｄｅｇｒｅｅ（ｖ　），其中（１≤ｉ≤ｎ）。定义　ｋｉｒｃｈｈｏｆｆ矩阵Ｈ＝Ｈ（Ｄ）为ｎｎ的矩阵，其中　ｈ　：』一　，ｉ≠ｊ并且从顶点、，ｊ到Ｖｉ有ｍｉｊ条边则　１　ｉｎｄｅｇｒｅｅ（ｖｉ）一ＩＩＩｉｊ，ｉ　ｊ　图Ｄ以ｖ　为根的生成树的个数等于ｈｋｋ的代数余子