论文部分内容阅读
由于多色有向图的本原性和本原指数与矩阵组的赫尔维茨积有紧密的联系,从而受到了广泛的关注.若D是一个多重有向图,且每条弧着有c1,c2,…ck中的一种颜色,则D为k-色多重有向图.对这样的图,若存在非负整数向量α=(α1,α2,…,αk)使得D中任意—对顶点u,v都存在一条从u到v的途径,它含有αi条颜色为ci的弧,i=1,2,…,k,则称D为本原的.并称α1+α2+…+αk的最小值为D的本原指数,记为exp(D).本文分三章,主要研究两类多色有向图的本原性和本原指数. 在第一章,我们先介绍了图论方面的主要的术语、记号,然后给出多色有向图的本原性和本原指数的定义及相应基本结果. 第二章第一节研究了双色有向图D*3的本原性,给出了D*3是本原的—个充要条件.在第二、三节中,我们研究了只有两条弧着颜色c2其余弧着颜色c1的D*3的本原指数.根据两条c2色弧的位置,本文将D*3分为类型1和类型2,并分别给出D*3为类型1和类型2时exp(D*3)的上界,主要结果如下: (1)如果D*3-图是类型1,该双色图的指数exp(D*3)≤8n2-2n-1. (2)如果D*3图是类型2,该双色图的指数exp(D*3)≤10n2-4n-3. 第三章第一节,我们研究了由k+1个长分别为b0+ka0,b0+a1,…,b0+ak的圈组成的(k+1)-色有向图D*,并给出了它是本原的充要条件.第二节给出了D*的本原指数,主要结果如下: (1)如果a0/a1+a0/a2+…+a0/ak+1/a1a2…ak=1,那么exp(D*)=2(ka0+1)a1a2…ak-1; (2)如果a0/a1+a0/a2+…+a0/ak-1/a1a2…ak=1,那么exp(D*)=2(ka0+1)a1a2…ak+1.