Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (6): 40-41.

• 学术探讨 • Previous Articles     Next Articles

The strong connectivity of a strong tournament

  

  • Received:2006-03-20 Revised:1900-01-01 Online:2007-02-21 Published:2007-02-21

强竞赛图的强连通性

王琦 刘晓姗 赵红銮   

  1. 山大数学与系统科学学院
  • 通讯作者: 王琦

Abstract: Let be a nonempty set and be a binary relation of . A directed graph is a pair , where is the vertex set of and is a collection of ordered pair of the vertices , called arcs. That can be reached from or can reach means there is a directed path from to . A strongly connected digraph is one in which any vertex can be reached from any other vertex by a directed path. A tournament is a directed graph in which there is exactly one arc between any two vertices. A strongly connected tournament is called a strong tournament. In this paper we discuss the property of the strong tournament with at least four vertices and give out another proof of Moon theorem by the particular property.

摘要: 是一个非空集, 是 上的二元关系,称有序对 为有向图,记为 .其中, 为顶点集, 为弧集, 中的元素是有序对 ,称为弧.设 和 是有向图 的两个顶点,若从 到 存在一条有向路,则称顶点 是从 可达的,或称从 可达 .若有向图 中任何两个顶点是互相可达的,则称 为强连通图.若有向图 中任意两个顶点之间恰有一条弧,则称 为竞赛图.一个强连通的竞赛图 称为强竞赛图.本文研究顶点个数大于 的强竞赛图 的性质,并利用该性质给出了Moon定理的另外一种证明.