论文部分内容阅读
作为现代数学的一个重要分支，图论在数学和其他科学领域中的作用都日益凸显。自上世纪30年代以来，关于图论的研究取得了长足的进步，得到了一大批重要的结果和新的理论。特别是上世纪70年代以后，随着计算机科学的发展，图论又被注入了新的活力，关于图论本身及其在物理，化学和计算机科学等领域中应用的研究都得到了惊人的发展。 不过，上世纪关于图论的研究主要是针对无向图的。近些年，随着有向图在数学和其他学科中的广泛应用，相关研究开始受到重视。不变量理论是有向图研究中的一个重要课题。本文考虑了有向图的张量积和状态分裂操作，对这两种操作下的不变量进行了研究，主要结果如下： 上世纪60年代，有向图的强连通性和单边连通性在张量积下的不变性都已被完全刻画，但关于张量积有向图弱连通性刻画的问题自1966年由Harary和Trauth提出以后，一直是有向图理论中的一个公开问题。本文通过引进有向图的权值和直径等参数，对张量积有向图的弱连通性给出了一个完全的刻画，从而回答了上述公开问题。 本原有向图是一类重要的有向图，其与道路着色定理和Markov链都有着密切的联系。在对使得张量积有向图弱连通的条件进行研究的基础上，本文将本原有向图的概念推广到广义本原有向图，证明了在强连通情形下这两个概念是等价的，并利用与关联矩阵相关的T-Sylvester方程的可解性给出了广义本原有向图的一个代数刻画。同时，对本原性和广义本原性在张量积下的不变性进行了刻画。 状态分裂是有向图中的一种重要操作，与符号动力系统有着密切的联系。本文利用有向图中的有向圈结构和有根森林结构，分别给出了加权有向图在状态入分裂和状态出分裂操作下的若干不变量。同时，对本原性和和广义本原性在状态分裂下的不变性进行了刻画。