竞赛图是通过在无向完全图中为每个边缘分配方向而获得的
有向图。 也就是说,它是一个完整图形的方向,等价于一个有向图,其中每对不同的顶点通过单个有向边连接,即每对顶点之间都有一条边相连的
有向图称为竞赛图。设D为n阶有向
简单图,若D中基图为n阶
无向完全图,则称D是n阶竞赛图。
简介
竞赛图是通过在无向完全图中为每个边缘分配方向而获得的
有向图。 也就是说,它是一个完整图形的方向,等价于一个有向图,其中每对不同的顶点通过单个有向边连接,即每对顶点之间都有一条边相连的
有向图称为竞赛图。
兰多(1953)首先调查了竞赛图的许多重要属性。竞赛图的当前应用包括投票理论和社会选择理论的研究等。 竞赛图起源于这样的图形解释:循环赛,其中每个玩家恰好一次遇到每个其他玩家。 在竞赛图中,顶点对应于球员。 每对玩家之间的边缘从胜者到失败者。 如果每个玩家都对阵同样数量的其他玩家,那么这个竞赛图就被称之为常规竞赛图。
路径和循环
任何有限数量n个顶点的竞赛图都包含一个哈密尔顿路径,即所有n个顶点上的直线路径。假设该语句适用于n,并考虑n + 1个顶点上的任何竞赛图T。 选择T的顶点v0,并考虑的一个有向路径。现在让是最大的,所以对于每个都有一个从到的有向边。
是根据需要设置的有向路径。 这个参数还给出了一种求解哈密尔顿算子的算法。 只需要检查边缘的。
这意味着紧密联系的竞赛图有一个哈密尔顿循环(Camion 1959)。 每个联系的竞赛图是顶点泛循环:对于每个顶点v,并且每个k在竞赛图中的三个到顶点的数量的范围内,存在包含v的长度为k的循环。此外,如果比赛是4连接的,则每对顶点可以与哈密尔顿路径连接(Thomassen 1980)。
传递性
在竞赛图中,被叫做一个传递。换句话说,在传递竞赛图中,顶点(严格地)由边缘关系完全排序。
等价条件
以下语句与n个顶点上的竞赛图T相当:
(1)T具有传递性;
(2)T是一个严格的总排序;
(3)T是非循环的;
(4)T不包含长度为3的循环;
(5)T的得分序列(外差集)为{0,1,2,...,n-1};
(6)T只有一个哈密尔顿路径。
拉姆齐理论
传递竞赛图在拉姆齐理论中起到类似于无向图中的作用。 特别是,n个顶点上的每个竞赛图在顶点上包含一个传递子公式。证明很简单:选择任何一个顶点v作为这个子公式的一部分,并在v的输入邻集或v的传出邻集之间递归地形成其余的子体,然后取较大者。
缩合
任何比赛的本身就是一场传递性的比赛。 因此,即使是不可传递的比赛,竞赛图的强力连接组件也可能被完全排序。
得分序列和分数集
比赛的得分序列是比赛顶点的不规则序列。 比赛的得分集是在该比赛中顶点的偏差的整数集合。
Landau的定理(1953):整数序列当且仅当满足下面条件的时候是一个得分序列:
让s(n)是大小为n的不同得分序列的数量。 序列s(n)(OEIS中的序列A000571)开始为:
温斯顿和克莱特曼证明,对于足够大的n:
其中c1= 0.049。
这些提供证据表明:
这里φ表示一个渐近紧的界限。