支撑多边形

支撑正方形问题提出，给定一个由四个等长杆组成的铰接正方形（如上图红线所示），为了使原始正方形在平面内变为刚性，需要在同一平面内添加多少根铰接杆（没有两根杆交叉）？已知的最佳解决方案（上图左侧）使用了总共 27 根杆（包括正方形的四根杆），其中 、 和 共线（Gardner 1964；Gardner 1984；Wells 1991；Fredrickson 2002，第 70 页，图 T4）。

对应于具有等长边（可以不妨假设为单位长度）且包含正多边形作为子图的刚性图的构型被称为支撑（正）多边形。虽然该问题的原始变体假设杆件不重叠，因此对应于刚性和火柴图的图嵌入，但放宽条件允许边重叠会得到对应于刚性单位距离图的解。

例如，如果允许杆件交叉以形成支撑正方形，则 A. Khodulyov 提出的最佳已知解决方案（如上图所示）需要 19 根杆（Friedman 2006）。

1963 年，T. H. O'Beirne 找到了五边形的火柴杆解决方案，使用 69 根杆，八边形使用 113 根杆，十二边形使用 57 根杆（Fredrickson 2002，第 70 页）。O'Beirne 的五边形支撑如上图所示（Fredrickson 2002，第 71 页，图 T6）。

可以不使用三角形来支撑正方形。上面说明的 21 边、12 节点单位距离图是通过从某个 29 节点对称支撑图（Pegg 2018b）进行顶点删除而构建的，它是无三角形的，并且支撑两个正方形（E. Pegg，私人通讯，2021 年 1 月 3 日）。此外，任何刚性框架（以及因此所有正多边形）都可以通过沿着两个共线边链接上面所示的 12 个 12 顶点无三角形支撑正方形的副本转换为无三角形的等效物（P. Taxel，2021 年 1 月 3 日）。

下表（从 Friedman 2006 更新，并删除了非刚性的 36 边 Mireles 图）给出了截至 2021 年 10 月的已知最小解决方案，包括杆件重叠和不重叠的情况。其中许多解决方案已在 Wolfram 语言中实现，如GraphData["BracedSquare",27,1], GraphData["BracedPentagon",69,1], 等等。

Khodulyov 对七边形和 11 边形的解决方案只是“等角”方法的实例，该方法使用 Peaucellier-Lipkin 连杆机构，适用于所有 -边形，其中 （n=8、9、10 和 12 除外，它们会产生顶点-顶点退化嵌入）。该结果是渐近最优的，需要 根杆（J. Tan，私人通讯，2021 年 10 月 26 日）。

	边	火柴杆	边	单位距离
3	3	三角形图 (简单情况)	3
4	27	七位发现者 (Gardner 1964)	19	Andrei Khodulyov (Friedman 2006)
5	69	T. H. O'Beirne，1963 年 (Fredrickson 2002, 第 70 页)	31	Andrei Khodulyov (Friedman 2006)
6	11	Friedman (2006；简单情况)	11
7			35	Ed Pegg, Jr.、Parcly Taxel、W. R. Somsky (2020 年 12 月)
8	113	T. H. O'Beirne，1963 年 (Fredrickson 2002, 第 70 页)	31	Andrei Khodulyov (Friedman 2006)
9			51	Andrei Khodulyov (Friedman 2006)
10			55	Andrei Khodulyov (Friedman 2006)
11			79	J. Tan (Parcly Taxel 2021)
12	57	T. H. O'Beirne，1963 年 (Fredrickson 2002, 第 70 页)	49	Andrei Khodulyov (Friedman 2006)
13			151	J. Tan (2021 年 10 月)
14			91	W. Somsky (2020 年 12 月)
15			231	Andrei Khodulyov (J. Tan, 2021 年 10 月)
16			109	J. Tan (2021 年 10 月)
17			269	Andrei Khodulyov (J. Tan, 2021 年 10 月)
18			117	J. Tan (2021 年 10 月)