论文部分内容阅读
对图进行代数性的表示及相关刻划是代数图论的中心课题之一.本文是在这一课题下针对有向图进行的研究和探讨.事实上,无向图可以可看作是对称有向图,即每条无向边对应方向互反,端点相同的两条弧.本文的研究工作主要分两部分,第一部分通过对有向图的几种不变量的讨论,对若干有向图类进行了研究并给出了一些代数表示与刻划.第二部分是对有向DeBruijn图这一特殊图类,给出了几种新的代数表示与刻划.
第一章概述了本文研究工作的相关背景和现状,以及本文的主要研究结果.第二章我们用矩阵等式的语言统一表示了有向图的同态映射,有向图覆盖,因子图,均匀划分等概念,并讨论了相应图类之间的关系.这一章的工作有独立的意义,同时也是为第三,四章的工作做准备.
第三至四章我们讨论了有向图覆盖的特征多项式.Gross和Tucker[80,81]指出,每一个对称有向图(正则)覆盖都可以通过对基图分配一个对称置换(普通)电压群而得到.这一结论推广到一般有向图也成立.我们突破了已有研究中电压群只能是有限Abel群的限制,对电压群是任意有限群的情况,给出了带半自由作用有向图的普通电压图表示,和分支指数为1的分支覆盖的置换电压图表示,并利用有限群表示论的知识,推导出了这两类图的特征多项式的分解公式.在以往的研究中提到,群作用有向图的特征多项式有一个因式与轨道图有关,但没有给出其几何意义,我们明确指出,该因式就是因子图的特征多项式.
Hoffman多项式是对强连通正则有向图定义的一个不变量[92],我们推广了这一概念,对任意非负不可约矩阵,包括一般的强连通有向图,定义了Hoffman多项式.我们明确提出了针对Hoffman多项式来研究有向图的判定性和刻划性两大类问题,并就此展开了具体的研究.这一部分内容集中在第五章.我们指出了Hoffman多项式与矩阵方程之间的关系,讨论了某些特殊图类对应的矩阵方程;并计算了有向图张量积的Hoffman多项式;探讨了两个初等等价矩阵的Hoffman多项式之间的关系,包括对有向线图及其基图,有向合并图和有向分裂图的相关表示和刻划;还针对一些特殊的多项式,研究了这些多项式成为有向图的Hoffman多项式的条件.
DeBruijn图[28]是有着丰富研究及应用背景的图类,在组合学,计算机网络,光纤通讯,自动机,分形学,量子计算等许多研究领域都受到关注.本文第六章从代数结构出发定义了一类陪集图,由此给出了有向DeBruijn图的一个代数表示及相应刻划,该刻划证实并推广了Fiduccia和Jacobson[64]提出的一个猜想.我们在第七章讨论了有向DeBruijn图的最优OTIS(光纤转换互联系统)布局,并部分地证明了Coudert等人提出的一个猜想[43].在现有的研究基础上,我们还提出了若干可进一步探讨的具体问题.