关于「补一条边的位置:贪心加边、菲德勒评分与数量的幻觉」,《谱间隙与瓶颈割集》给出的定量结论是什么?

结论:第三章逐条试算新边,跨队边的平均增量是队内边的 87.5 倍。

数据口径:书中参数为示意;全部计算由书中程序生成;本书是非个人化经营建议,任何生产系统或真实供应链的改动须由主事者人工复核放行。 第八章给出画图、体检、补边、复查的季度闭环,示意工作流三轮补边后代数连通度从 0.1824 升到 1.0000;蒸馏小工具「瓶颈割集体检器」;以及每组 74 个团队季度的预注册检验方案与推翻条件。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 87.5

base25 edges, lambda2 = 0.24123, 41 absent edges tried
rank edge kind lambda2 gain Fiedler score score rank
1 ( 3, 9) cross0.29467 0.40338 1
2 ( 1, 9) cross0.27342 0.37942 2
3 ( 2, 9) cross0.27342 0.37942 3
4 ( 3, 7) cross0.27342 0.37942 4
5 ( 3, 8) cross0.27342 0.37942 5
41 ( 8,11) inside0.00000 0.00000 41
inside-team edges6, mean gain 0.00275, max 0.00824
cross-team edges35, mean gain 0.24033, max 0.29467, min 0.18366
best / worst cross-team gain1.60
mean cross gain / mean inside gain87.5
查看完整验算程序
# Chapter 3. p31: try every possible single new edge on a two-team
# network and rank the gain in lambda2; compare with the Fiedler-vector
# score (f_i - f_j)^2 used as a first-order guide by Ghosh and Boyd.
# Model: two teams of six, each team K6 minus a perfect matching (every
# member linked to four of five team-mates), one liaison edge (0, 6).
# Exact gains by Jacobi rotation for all 41 absent edges. Illustrative.
import math


def laplacian(n, edges):
    lap = [[0.0] * n for _ in range(n)]
    for i, j in edges:
        lap[i][j] -= 1.0
        lap[j][i] -= 1.0
        lap[i][i] += 1.0
        lap[j][j] += 1.0
    return lap


def jacobi(mat, tol=1e-22):
    n = len(mat)
    a = [row[:] for row in mat]
    v = [[1.0 if i == j else 0.0 for j in range(n)] for i in range(n)]
    sweeps = 0
    while True:
        off = math.fsum(a[i][j] ** 2 for i in range(n)
                        for j in range(i + 1, n))
        if off < tol or sweeps > 60:
            break
        sweeps += 1
        for p in range(n - 1):
            for q in range(p + 1, n):
                if abs(a[p][q]) < 1e-300:
                    continue
                th = (a[q][q] - a[p][p]) / (2.0 * a[p][q])
                t = math.copysign(1.0, th) / (abs(th) + math.hypot(th, 1.0))
                c = 1.0 / math.sqrt(t * t + 1.0)
                s = t * c
                for k in range(n):
                    akp, akq = a[k][p], a[k][q]
                    a[k][p] = c * akp - s * akq
                    a[k][q] = s * akp + c * akq
                for k in range(n):
                    apk, aqk = a[p][k], a[q][k]
                    a[p][k] = c * apk - s * aqk
                    a[q][k] = s * apk + c * aqk
                for k in range(n):
                    vkp, vkq = v[k][p], v[k][q]
                    v[k][p] = c * vkp - s * vkq
                    v[k][q] = s * vkp + c * vkq
    order = sorted(range(n), key=lambda i: a[i][i])
    vals = [a[i][i] for i in order]
    vecs = [[v[k][i] for k in range(n)] for i in order]
    return vals, vecs, sweeps


def team(off):
    es = []
    for a in range(6):
        for b in range(a + 1, 6):
            if b - a != 3:
                es.append((a + off, b + off))
    return es


n = 12
base_edges = team(0) + team(6) + [(0, 6)]
present = set(base_edges)
vals, vecs, _ = jacobi(laplacian(n, base_edges))
lam0, f = vals[1], vecs[1]
cands = [(i, j) for i in range(n) for j in range(i + 1, n)
         if (i, j) not in present]
rows = []
for i, j in cands:
    lam = jacobi(laplacian(n, base_edges + [(i, j)]))[0][1]
    kind = "cross" if (i < 6) != (j < 6) else "inside"
    g = lam - lam0
    if abs(g) < 1e-12:
        g = 0.0
    rows.append((g, (f[i] - f[j]) ** 2, i, j, kind))
by_score = sorted(rows, key=lambda r: (-round(r[1], 9), r[2], r[3]))
srank = {(r[2], r[3]): k + 1 for k, r in enumerate(by_score)}
rows.sort(key=lambda r: (-round(r[0], 9), r[2], r[3]))
print("base: %d edges, lambda2 = %.5f, %d absent edges tried"
      % (len(base_edges), lam0, len(cands)))
print("rank  edge     kind     lambda2 gain  Fiedler score  score rank")
for k in (0, 1, 2, 3, 4, len(rows) - 1):
    g, sc, i, j, kind = rows[k]
    print("%4d  (%2d,%2d)  %-6s   %10.5f   %11.5f   %6d"
          % (k + 1, i, j, kind, g, sc, srank[(i, j)]))
inside = [r[0] for r in rows if r[4] == "inside"]
cross = [r[0] for r in rows if r[4] == "cross"]
print()
print("inside-team edges: %2d, mean gain %.5f, max %.5f"
      % (len(inside), math.fsum(inside) / len(inside), max(inside)))
print("cross-team edges:  %2d, mean gain %.5f, max %.5f, min %.5f"
      % (len(cross), math.fsum(cross) / len(cross), max(cross),
         min(cross)))
print("best / worst cross-team gain: %.2f"
      % (max(cross) / min(cross)))
print("mean cross gain / mean inside gain: %.1f"
      % (math.fsum(cross) / len(cross) / (math.fsum(inside) / len(inside))))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《图拉普拉斯谱间隙、奇格常数与多智能体工作流及跨国供应链单点瓶颈割集母典》第 3 章「补一条边的位置:贪心加边、菲德勒评分与数量的幻觉」(版本 1.0.0). 5D Library. DOI 待发布

DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-243 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026243,
  author    = {Fan, Yafu},
  title     = {Graph-Laplacian Spectral Gaps and Cheeger Constants: Single-Point Bottleneck Cuts in Multi-Agent Workflows and Cross-Border Supply Chains},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

本书其他章节结论