竞赛图是完全无向图的定向图,具有任意两个顶点之间有且仅有一条弧的性质.竞赛图的控制图和竞争图有比较紧密的联系,对竞赛图的控制图的研究由来已久,并在生物竞争图的结构刻画上起到了重要的作用.设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 ver-tices and tournaments S i ,i =1,2,…,c .Let D =T [S 1 ,S 2 ,…,S c ]denote the combined tourna-ment of T .In this paper,we focus on the properties and structure of domination graph of com-bined tournaments.Based on current results,we present an efficient algorithm for the domination graph of a combined tournament.
展开▼
