局部几乎正则多部竞赛图中的分量共轭圈  

Componentwise complementary cycles in locally almost regular multipartite tournaments

作　　者：何志红[1,2] 李国君[3] 李曙光[4] 

机构地区：[1]山东大学计算机科学与技术学院,山东济南250101 [2]烟台大学数学与信息科学学院,山东烟台264005 [3]山东大学数学与系统科学学院,山东济南250100 [4]山东工商学院信息与电子工程学院,山东烟台264005

出　　处：《系统工程与电子技术》2009年第10期2513-2515,共3页Systems Engineering and Electronics

基　　金：国家自然科学基金(60373025)资助课题

摘　　要：一个n-部竞赛图是n-部完全图的一个定向。令V1,V2,…,Vn是n-部有向图D的部集。如果D中存在两个不相交的圈C和C′使得对于每一个i∈{1,2,…,n}都有Vi∩(V(C)∪V(C′))≠Φ,则称C和C′是D的一对分量共轭圈。针对多部竞赛图的共轭圈问题,提出了分量共轭圈的定义,同时证明了每一个至少有6个顶点的部集具有相等基数的局部几乎正则多部竞赛图的分量共轭圈的存在性问题。An n partite tournament is an orientation of a complete n-partite graph. Let V1 ,V2, … ,Vn be the partite sets of D. If there exist two vertex disjoint outpaths C and C′ in D such that Vi ∩ （V（C） ∪V（C′））≠Ф for all i∈ { 1,2,… ,n}, then C and C′ are a pair of componentwise complementary outpaths of D. For the complementary cycles problems of multipartite tournaments presents the definition of componentwise complementary cycles, proves the existing problem of componentwise complementary cycles of locally almost regular multipartite tournaments that has at least six vertices and the same partite sets cardinality.

关 键 词：运筹学 分量共轭圈 贪心算法 共轭圈 局部几乎正则的 多部竞赛图 

分 类 号：O157.5[理学—数学]