M21
多部竞赛图中不相交圈的最小出度条件：Bermond–Thomassen 型命题的机器穷举与小情形证明
来源说明：本则出自独立撰写的第二批方案。它与前 20 则同样遵循八块结构与硬门槛要求，但撰写时未做英文文献检索，新颖性边界依据的是历届获奖图谱与既有知识，而非当轮查新。因此其「需核实」条目更多，启动前须自行补一轮英文检索。
1 · 研究问题
对 3-部竞赛图（3-partite tournament，即完全 3 部图的定向），最小出度 δ⁺ ≥ 3 是否已保证存在两个顶点不相交的有向圈？更进一步：Bermond–Thomassen 型条件"δ⁺ ≥ 2k−1 保证 k 个不相交圈"在多部竞赛图类中最小能到多强（能否把 2k−1 降低）？
2 · 研究背景与空白
竞赛图（tournament）是完全图的定向，多部竞赛图是完全多部图的定向。Bermond–Thomassen 猜想（1981）断言：任何最小出度 δ⁺ ≥ 2k−1 的有向图含 k 个顶点不相交的有向圈。这是有向图论的中心猜想之一，"不相交圈"是可精确判定的组合对象，非常适合机器验证。
已有工作：一般有向图的 k = 2 情形已被证明（Thomassen，1983，需核实：搜索关键词 Thomassen disjoint cycles digraph minimum outdegree 3）；竞赛图类上该猜想已完整解决（需核实：搜索关键词 Bermond-Thomassen conjecture tournaments proof）。丘奖内部：2020 年优胜奖论文《Disjoint Cycles in Ordinary Multipartite Tournaments and Round-Robin Tournaments》研究了普通多部竞赛图中不相交圈的存在条件；2025 年入围论文《On an inverse problem of Bermond's Conjecture》做的是逆问题方向。
空白在：多部竞赛图这一中间类上，该命题既没有系统的机器穷举图景，小 k 情形也未见完整的初等证明整理（需核实：搜索关键词 disjoint cycles multipartite tournaments minimum out-degree）。适合学生：对象可穷举、反例本身也是有效结论、所需工具是初等图论归纳。
3 · 可检验假设
- H1：每部大小 ≤ 4、总阶 n ≤ 12 的全部非同构 3-部竞赛图中，δ⁺ ≥ 3 者均含 2 个不相交圈（即该范围内无反例）。
- H2（备择/机制）：若存在反例，其必含一个"近乎传递"的被支配部类；据此可刻画 δ⁺ = 2 时无 2 个不相交圈的极值构型族。
4 · 量化验收标准
- 方法学校验（硬门槛）：自建穷举管线先在竞赛图上复现已知事实——n ≤ 9 全部非同构竞赛图（n = 9 时共 191,536 个，OEIS A000568）中，δ⁺ ≥ 3 者全部含 2 个不相交圈，且复现 δ⁺ = 2 时的已知反例结构。此步不过关，后续全部结论无效。
- 穷举覆盖：3-部竞赛图、各部大小 ≤ 4 且 n ≤ 12，同构消重（nauty），给出总数报告与逐条判定日志，第三方一键复跑。
- 证明交付：k = 2、3-部情形给出完整证明，或给出反例 + 极值构型刻画定理；论文中明确标注哪些命题是严格证明、哪些是穷举证据。
- SAT 反例搜索扩展到 n ≤ 18（不完备搜索，随机种子固定、编码开源、可复现）。
- 全部代码与生成数据开源，README 含一键重跑脚本。
5 · 数据与工具
| 用途 | 来源 / 工具 |
|---|---|
| 图生成与同构消重 | nauty/Traces 套件（geng、directg、watercluster2），pallini.di.uniroma1.it 免费下载，纯 CPU |
| 圈检测与图操作 | Python + NetworkX / igraph（pip 安装）；核心判定用位运算自写以提速 |
| SAT 反例搜索 | PySAT（pip install python-sat）+ Kissat 求解器（GitHub 开源） |
| 竞赛图计数对照 | OEIS A000568（仅用于校验管线，不计入本项目贡献） |
| 算力量级 | n ≤ 12 的 3-部竞赛图判定约 10⁷–10⁸ 次，位运算优化后笔记本数小时–数天可完成 |
6 · 方法路径
- 装 nauty 与 PySAT，跑通 geng/directg 内置算例，完成第 4 块第 1 条校验。
- 实现"k 个不相交圈"判定器（k = 2 用圈枚举 + 二分匹配剪枝），与暴力枚举在 n ≤ 7 交叉验证。
- 穷举 3-部竞赛图 n ≤ 12，记录 δ⁺ 分布与反例候选。
- 归纳穷举结果，提炼 δ⁺ = 2 极值构型的结构猜想，尝试 k = 2 完整证明（按部类支配关系分类讨论）。
- SAT 编码扩展搜索 n ≤ 18，核实结构猜想在更大范围的稳定性。
- 独立交叉校验：用 igraph 的独立实现复算全部反例候选；写明严格证明与计算证据的边界。
7 · 新颖性边界
- 本课题不声称解决 Bermond–Thomassen 猜想，也不声称竞赛图情形（已解决）为本项目结果。
- 已有工作：一般有向图 k = 2 已证；竞赛图类已完整解决（具体文献第 2 周核实并引用）。丘奖相邻获奖论文：2020《Disjoint Cycles in Ordinary Multipartite Tournaments and Round-Robin Tournaments》（存在性条件方向）、2025《On an inverse problem of Bermond's Conjecture》（逆问题方向）——本题与前者的差异是限定 3-部 + 系统机器穷举 + 完整小情形证明为主交付，与后者的差异是做正问题的类限制版本。
- 本项目贡献（主结论）：多部竞赛图小情形的可判定定理图景 + k = 2 的完整证明或极值构型刻画。
- 价值：为中心猜想在一个自然图类上提供第一份系统的穷举证据与初等证明整理；无反例与有反例都是有效结论。
8 · 决策门槛（go / no-go）
- 第 4 周末：完成硬门槛校验（竞赛图 n ≤ 9 复现零反例）。未通过 → 停下修管线，这是工程问题不是课题问题；连续 2 周未通过则请老师协助排查判定器逻辑。
- 第 10 周末：若 k = 2 证明无实质进展且穷举 n ≥ 12 已无反例，降级路径 A：主结论改为"δ⁺ = 2 极值构型的完整刻画 + 穷举图景"（保留同一管线与结论框架）；降级路径 B：改证更强条件 δ⁺ ≥ 4 下的 2 个不相交圈（结论弱化但仍是定理）。
- 第 2 周核实项：竞赛图情形与 k = 2 一般情形的原始文献；多部竞赛图上是否已有同型定理（若有，转向该定理未覆盖的部数/度条件组合，框架不变）。
- 第 20 周锁定主定理陈述；第 36 周中文全文成稿；第 44 周英文稿与答辩术语表。
- 预算裁剪顺序：先砍 SAT 扩展搜索（第 4 条），再砍 n = 12 层（降到 n ≤ 11），主结论仍成立。