竞赛图(tournament),理学-数学-图论-次模函数-线图,给完全图的每条边一个定向,则所得的有向图称为竞赛图。被称为竞赛图是因为这类图可以被视为某个循环赛(每个队都与其他队各赛一次且无平局)的结果,其中,竞赛图的顶点代表参赛的队,有向边由胜者指向败者。每个有限竞赛图都存在一条有向哈密顿路,即一条包含图的所有顶点的有向路。强连通的竞赛图则存在一个有向哈密顿圈。还有一个更强的结论是,含有个顶点的强连通竞赛图都是点泛圈图,即对每个和,中存在包含的长圈。在竞赛图中,用表示图的弧集,若由能得到,则称是传递的。下面是有关传递性的一些等价条件:①竞赛图是传递的;②不含有向圈;③不含3长圈;④的顶点出度序列为,式中;⑤恰有一条有向哈密顿路。竞赛图有很多实际的应用,包括投票理论和社会选择理论等。