竞赛图

竞赛图就是给一个完全图的所有边指定一个方向的图。

至于为什么叫“竞赛”图,大概是因为一条边代表两个人之间比赛的输赢情况吧。

这种图有一些比较优美的性质:

  1. 竞赛图必定有哈密顿路径。

  2. 如果竞赛图强连通,则它必有哈密顿回路。

  3. 如果竞赛图有一个大小为 \(k (k>3)\) 的环,那么一定有大小为 \(k-1\) 的环。

  4. 将竞赛图缩点后,将会得到一个 DAG,并且这个 DAG 有一条哈密顿路径(也可以理解为这是一条链,并且前面的点可以连向后面任意节点)。

然而有了这些性质我还是做不出题。

上一篇:bat 读取 ini 文件


下一篇:android微信摇一摇(抽奖)