论文标题
最佳电阻网络
Optimal Resistor Networks
论文作者
论文摘要
给定一个带有M边缘的N顶点上的图形，每个单位电阻，顶点对之间的平均电阻可以多大？有两个非常合理的极端结构 - 图形如恒星，并且图形接近常规的图 - 当平均度为3时，它们之间发生过渡。但是，本文中我们的主要目的之一是表明，平均程度范围的构建范围明显更好，包括平均水平，包括平均水平接近3。 一个关键的想法是将此问题与有关根系图的类似问题联系起来 - 即``根生根图都可以最小化对根的平均电阻吗？”。与未根本的情况相比，植根的情况要简单得多，本文的主要结果之一是两种情况在渐近上等效。
Given a graph on n vertices with m edges, each of unit resistance, how small can the average resistance between pairs of vertices be? There are two very plausible extremal constructions -- graphs like a star, and graphs which are close to regular -- with the transition between them occuring when the average degree is 3. However, one of our main aims in this paper is to show that there are significantly better constructions for a range of average degree including average degree near 3. A key idea is to link this question to a analogous question about rooted graphs -- namely `which rooted graph minimises the average resistance to the root?'. The rooted case is much simpler to analyse than the unrooted, and one of the main results of this paper is that the two cases are asymptotically equivalent.
