最小团覆盖问题：如何生成非平凡测试用例？

要构造已知最小团覆盖数及节点最优分配的图，核心思路是从团划分的目标出发，反向构造图结构，确保无法用更少的团完成覆盖。以下是几种实用的构造方法：

方法1：不相交完全图的并集 #

这是最直接的构造方式，适合验证基础场景：

• 构造步骤：
  1. 确定目标最小团覆盖数k，以及每个团的大小（比如设为m₁, m₂, ..., mₖ，总节点数n = m₁+m₂+...+mₖ）。
  2. 创建k个互不相交的完全图C₁, C₂, ..., Cₖ，其中Cᵢ包含mᵢ个节点，且不同Cᵢ与Cⱼ之间无任何边。
• 已知参数：
  • 最小团覆盖数为k：每个Cᵢ本身是团，必须用单独的团覆盖（跨Cᵢ和Cⱼ的节点无连接，无法放入同一个团）。
  • 最优分配：每个Cᵢ的所有节点属于同一个团。
• 示例：3个不相交的完全图，分别含2、3、4个节点，总节点9个，最小团覆盖数为3，每个团对应一个完全图的所有节点。

方法2：利用补图的着色等价性 #

最小团覆盖问题等价于补图的顶点着色问题（团覆盖中的每个团对应补图中的一个独立集，即着色中的一个颜色类）。利用这个等价性可以构造更复杂的测试用例：

• 构造步骤：
  1. 选择一个色数为k的图H（比如奇数圈、完全k部图等）。
  2. 构造H的补图G：G中两个节点相邻当且仅当它们在H中不相邻。
• 已知参数：
  • 最小团覆盖数为k：因为H的色数是k，意味着H无法用少于k种颜色着色，对应G无法用少于k个团覆盖。
  • 最优分配：H中同颜色的节点在G中构成一个团，直接作为覆盖中的一个团。
• 示例：
  取H为5节点的奇数圈（节点1-2-3-4-5-1），其色数为3，颜色分配为：1(红)、2(蓝)、3(红)、4(蓝)、5(绿)。补图G中，红色节点{1,3}两两相邻、蓝色节点{2,4}两两相邻、绿色节点{5}是团，这3个团构成最小覆盖，无法用2个团完成覆盖。

方法3：带公共节点的分层团结构 #

这种构造能生成更“非平凡”的图，最优分配存在多种方式但最小覆盖数固定：

• 构造步骤：
  1. 确定目标最小团覆盖数k。
  2. 创建一个公共节点v，再创建k个互不相交的完全图C₁, C₂, ..., Cₖ。
  3. 让v与所有Cᵢ中的节点相连，不同Cᵢ与Cⱼ之间无连接。
• 已知参数：
  • 最小团覆盖数为k：可以用k个团（每个团为{v} ∪ Cᵢ）覆盖所有节点；若尝试用k-1个团，至少有一个团要包含来自两个不同Cᵢ的节点，而这些节点无连接，无法构成团。
  • 最优分配：每个团包含公共节点v和一个Cᵢ的所有节点（或也可将v单独作为一个团，再用k个团覆盖Cᵢ，但这是k+1个团，不是最优）。

方法4：二分图的构造（基于Konig定理） #

对于二分图，最小团覆盖数 = 总节点数 - 最大匹配数，利用这个定理可以精准构造：

• 构造步骤：
  1. 确定目标最小团覆盖数k，设总节点数为n，则最大匹配数为n - k。
  2. 构造一个二分图，使其最大匹配数恰好为n - k（比如构造k个不相交的边，总节点数2k，最大匹配数k，则最小团覆盖数为2k - k = k）。
• 已知参数：
  • 最小团覆盖数为k，最优分配为选取k条边（构成匹配）作为团，覆盖所有节点。

内容的提问来源于stack exchange，提问作者MarcoM