组合竞赛图的控制图  

Domination Graph of a Combined Tournament

作　　者：张云霞[1] 杨卫华 

机构地区：[1]山西省财政税务专科学校,太原030024 [2]太原理工大学数学学院,太原030024

出　　处：《太原理工大学学报》2017年第6期1029-1032,共4页Journal of Taiyuan University of Technology

基　　金：国家自然科学基金资助项目(11671296)

摘　　要：竞赛图是完全无向图的定向图,具有任意两个顶点之间有且仅有一条弧的性质。竞赛图的控制图和竞争图有比较紧密的联系,对竞赛图的控制图的研究由来已久,并在生物竞争图的结构刻画上起到了重要的作用。设T是c个顶点的竞赛图,S_i(i=1,2,…),c分别是竞赛图,那么称D=T[S_1,S_2,…,S_c]为T的组合竞赛图。通过研究组合竞赛图的控制图的性质和结构,对原有针对竞赛图的定理进行扩充,针对如何求解竞赛图的控制图,推导并求解组合竞赛图的控制图,并给出相应算法。A tournament is a directed graph(digraph)obtained by assigning a direction for each edge in an undirected complete graph.There is a close relationship between domination graph and competition graph of tournaments.The exploration of domination graphs has played an important role in biology research of species competition graph.Given a tournament T with c vertices and tournaments S_i,i=1,2,…,c.Let D=T[S_1,S_2,…,S_c]denote the combined tournament of T.In this paper,we focus on the properties and structure of domination graph of combined tournaments.Based on current results,we present an efficient algorithm for the domination graph of a combined tournament.

关 键 词：竞赛图 组合竞赛图 控制图 

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