论文部分内容阅读
图论和非负矩阵理论是组合数学中的两个重要研究内容,这两个内容有着密切的联系.非负矩阵A与它对应的伴随有向图D(A)具有一一对应关系.多色有向图的本原性和本原指数与矩阵簇的赫尔维茨积也有紧密的联系,
若D是一个多重有向图,且每条弧着有C1,C2,…,ck(k=1,2,3,…)中的一种颜色,则D称为k-色多重有向图,对这样的图,若存在非负整数向量α=(α1,α2,…,αk)使得D中任意一对顶点u,v都存在一条从u到v的途径,它含有αi条颜色为ci的弧,i=1,2,…,k,则称D为本原的.并称α1+α2+…+αk的最小值为D的本原指数,记为exp(D)。
本文分四章,主要研究几类多色有向图的本原性和本原指数。
在第一章,我们先介绍了图论方面的主要的术语、记号,由图与非负矩阵的关系引入了有向图的本原矩阵与本原指数的相关知识及其在国内外研究概况,提出了本文所做的工作。
第二章介绍了一类双色Wielandt有向图的本原指数和一类含双圈的双色有向图的本原性。
第三章研究了一类特殊的三色有向图,其含有奇数个顶点,其未着色图恰含一个n-圈、一个(n-2)-圈和一个2-圈,给出了在一种本原条件下的三色有向图的本原指数紧的上界.并进行了极图刻划。
第四章介绍了一类(k+1)-色有向图的本原问题,并对本文内容作出总结,提出进一步的问题。