如何根据有向图的边数计算所需的最小节点数？

给定有向图的边数Y，我们需要找到能容纳至少Y条边的最小整数节点数X。核心依据是完全有向图的边数规则：X个节点的完全有向图总边数为 X*(X-1)（每个节点都有指向其余所有节点的有向边）。

推导步骤 #

1. 明确需求：找到最小整数X，满足不等式 X*(X-1) ≥ Y
2. 将不等式转化为二次方程形式：X² - X - Y ≥ 0
3. 通过二次方程求根公式，计算正根：X = [1 + √(1 + 4Y)] / 2
4. 对计算结果向上取整，得到满足要求的最小整数节点数

实际示例 #

• 当Y=5时：(1+√21)/2≈2.79，向上取整为3，3个节点可提供6条边，满足容纳5条边的需求
• 当Y=6时：(1+√25)/2=3，刚好取整为3，完全匹配边数
• 当Y=7时：(1+√29)/2≈3.19，向上取整为4，4个节点可提供12条边，满足需求

代码实现（Python） #

import math

def get_min_digraph_nodes(edge_count):
    discriminant = 1 + 4 * edge_count
    sqrt_disc = math.sqrt(discriminant)
    x = (1 + sqrt_disc) / 2
    return math.ceil(x)

验证 #

调用get_min_digraph_nodes(5)返回3，get_min_digraph_nodes(6)返回3，get_min_digraph_nodes(7)返回4，均符合预期。

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