IBM Ponder This #323 · 2025 年 3 月

Hugo Pfoertner 提出了这个问题。把有限无向图视为电阻网络，允许重边，每条边电阻同为 $R$。对给定 $n$，选择 $n$ 个指定节点，要求它们两两等效电阻互不相同；允许有不计入 $n$ 的辅助节点。

例如下图测量节点 $1\dots 5$，取 $R=47$ 时，得到 $[19,20,31,33,35,39,40,45,46,52]$，共 $10=\frac{n(n-1)}{2}$ 个不同值：

边列表为：

[(1, 6), (1,4), (2,5), (2,6), (3,5), (3,5), (3,6), (4,5), (4,5)]

默认编号 $1,2,\dots ,n$ 是被测节点，其余为辅助节点。该例九条边并非最优，最优为八条。额外要求任一节点不能只有一个不同邻居。

任务：$n=10$ 时，用最少边数使节点 $1,\dots ,10$ 间有 45 种不同电阻，给边列表。

附加问题：$n=12$、66 种电阻时，找出最优的全部三个平面图方案，以及一个非平面图方案。

解答

认真尝试后再打开

待补充。