Python最小边数图构建算法的正确性验证及证明咨询

算法正确性结论 #

该算法是正确的——只要输入保证存在合法解，按此方法必然能构造出满足所有条件且边数最少的图。

正确性证明 #

1. 最优图的核心结构

满足要求的最小边数图只有两种核心形态：

• 星型结构：一个中心节点连接所有其他节点，边数为n-1，图直径为1（完全符合“任意两节点最多2条边可达”的要求）。这是边数最少的理想情况，只要不存在与中心相关的禁止边，直接用这种结构即可。
• 扩展星型结构：如果中心节点无法连接部分节点（记为集合T），则必须满足两个子条件：
  • T中的每个节点至少能连接到一个与中心连通的节点（记为集合S，即中心合法连接的节点）；
  • T内任意两节点的距离≤2——要么所有T节点都连接同一个S节点（通过该节点间接连通，距离为2），要么T本身是一个团（两两直接连通，距离为1）。
    这两种扩展结构的边数要么等于n-1（前者），要么为|S| + C(|T|,2)（后者），都是当前约束下的最小可能值。

2. 按可连接数选中心的合理性

节点的“可连接数”指它能合法连接的其他节点数量（排除禁止边后的最大邻居数）。优先选可连接数最多的节点当中心，有两个关键逻辑支撑：

• 该节点的S集合最大、T集合最小，需要额外处理的节点更少，更容易满足扩展星型结构的约束；
• 若输入存在合法解，那么对于可连接数最多的节点u，其T集合中的每个节点必然能找到至少一个S中的节点与之连通——否则该节点无法与中心u形成≤2的路径，直接违反条件2，与输入存在合法解的前提矛盾。

3. 算法的终止性与正确性

由于输入保证存在合法解，必然存在至少一个节点能作为中心满足结构约束。按可连接数从大到小尝试时，第一个满足条件的节点就能构造出边数最少的图：

• 若存在S中的节点能连接所有T节点，构造的图边数为n-1，达到理论最小值；
• 若T本身是团，则构造的图边数为|S| + C(|T|,2)，这是当前约束下的最小边数（若不采用团结构，T节点间距离会超过2，违反条件）。
  反过来，如果可连接数最多的节点都无法满足约束，那么可连接数更少的节点（S更小、T更大）更不可能满足，这与输入存在合法解的前提矛盾，因此算法必然能找到可行的中心节点。

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