循环赛构成圈的个数

abababa

$n$个人比赛，每两人赛一场，如果有$i$胜$j$，$j$胜$k$，$k$胜$i$，则称$ijk$三人构成一个圈。用$w_i$表示第$i$人胜的次数，问这个比赛中有多少个圈。

Czhang271828

将该图视作有向图, 则图中有 $\binom{n}{3}$ 个三角形. 我们希望找到所有连边形如 $a\to b\to c\to a$ 的三角形 (好三角). 注意到以下三类对象是等价的:

(1) 一个不好的三角形,
(2) 一条形如 $b\gets a\to c$ 的路,
(3) 某人的两个手下败将间的一场比赛.

显然 (1) 与 (2) 等价, (2) 与 (3) 等价. 因此好三角的数量是
$$
\binom{n}{3}-\sum_{i=1}^n\binom{w_i}{2}.
$$

-----------------

矩阵做法似乎也可以.

记 $A$ 是邻接矩阵, 则
$$
A+A^T+I=1\cdot 1^T=:J.
$$
特别地, $\mathrm{tr}(A)=0$, $\mathrm{tr}(A^2)=0$, $\mathrm{tr}(A^3)=3\cdot \text{好三角数}=:3|\triangle|$. 计算
$$
\mathrm{tr}(A^3+(A^T)^3)=\mathrm{tr}(A^3+(J-I-A)^3)
$$
即可. 记维数向量 $w=A\cdot 1$, $|w|=1^T\cdot w$. 依照 $\mathrm{tr}(PQ)=\mathrm{tr}(QP)$, 上式为
$$
\mathrm{tr}(J^3-3J^2A+3JA^2-3J^2+6JA-3A^2+3J-3A-I).
$$
去掉明显为零的项, 计算容易计算的量, 得
$$
n^3-3n^2+2n+3\cdot \mathrm{tr}(-J^2A+JA^2+2JA).
$$
依照
(1) $\mathrm{tr}(J^2A)=\mathrm{tr}(AJ^2)=\mathrm{tr}(w\cdot 1^T\cdot J)=n|w|$.
(2) $\mathrm{tr}(JA^2)=\mathrm{tr}((A1)\cdot (A^T1)^T)=w^T\cdot (n-1-w)=(n-1)|w|-w^Tw$.
(3) $\mathrm{tr}(JA)=\mathrm{tr}(A11^T)=|w|$.
原式 ($6|\triangle|$) 为
$$
n^3-3n^2+4n+3(|w|-w^Tw)=n(n-1)(n-2)-3\sum_{i=1}^nw_i(w_i-1).
$$
和纯图论的方法一致.

-----------------
也可以找到最大值的上界. 偶数情况置 $w_i\in \{\frac{n}{2},\frac{n-2}{2}\}$, 则 $|\triangle|\leq \frac{n^3-4n}{24}$; 奇数情况置若干 $w_i=\frac{n-1}{2}$, 则 $|\triangle|\leq \frac{n^3-n}{24}$.

abababa

Czhang271828 发表于 2024-9-5 16:37
将该图视作有向图, 则图中有 $\binom{n}{3}$ 个三角形. 我们希望找到所有连边形如 $a\to b\to c\to a$ 的三 ...

原来如此，是考察反面的情况。