计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (6): 40-41.

• 学术探讨 • 上一篇    下一篇

强竞赛图的强连通性

王琦 刘晓姗 赵红銮   

  1. 山大数学与系统科学学院
  • 收稿日期:2006-03-20 修回日期:1900-01-01 出版日期:2007-02-21 发布日期:2007-02-21
  • 通讯作者: 王琦

The strong connectivity of a strong tournament

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

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

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.