关于「补一条边的位置:贪心加边、菲德勒评分与数量的幻觉」,《谱间隙与瓶颈割集》给出的定量结论是什么?
结论:第三章逐条试算新边,跨队边的平均增量是队内边的 87.5 倍。
数据口径:书中参数为示意;全部计算由书中程序生成;本书是非个人化经营建议,任何生产系统或真实供应链的改动须由主事者人工复核放行。 第八章给出画图、体检、补边、复查的季度闭环,示意工作流三轮补边后代数连通度从 0.1824 升到 1.0000;蒸馏小工具「瓶颈割集体检器」;以及每组 74 个团队季度的预注册检验方案与推翻条件。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 87.5
| base | 25 edges, lambda2 = 0.24123, 41 absent edges tried |
| rank edge kind lambda2 gain Fiedler score score rank | |
| 1 ( 3, 9) cross | 0.29467 0.40338 1 |
| 2 ( 1, 9) cross | 0.27342 0.37942 2 |
| 3 ( 2, 9) cross | 0.27342 0.37942 3 |
| 4 ( 3, 7) cross | 0.27342 0.37942 4 |
| 5 ( 3, 8) cross | 0.27342 0.37942 5 |
| 41 ( 8,11) inside | 0.00000 0.00000 41 |
| inside-team edges | 6, mean gain 0.00275, max 0.00824 |
| cross-team edges | 35, mean gain 0.24033, max 0.29467, min 0.18366 |
| best / worst cross-team gain | 1.60 |
| mean cross gain / mean inside gain | 87.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}
}