查看“WikiEdge:ArXiv-1904.12761”的源代码

* '''标题'''：The graphs behind Reuleaux polyhedra
* '''中文标题'''：Reuleaux多面体背后的图
* '''发布日期'''：2019-04-29 15:06:13+00:00
* '''作者'''：Luis Montejano, Eric Pauli, Miguel Raggi, Edgardo Roldán-Pensado
* '''分类'''：cs.CG, math.CO
*'''原文链接'''：http://arxiv.org/abs/1904.12761v1
'''摘要'''：本文研究了由Reuleaux多面体产生的图。这样的图必须是平面的，3连通的，且强自对偶的。我们研究了这些条件何时足够的问题。
如果$G$是具有同构$\tau : G \to G^*$的图（其中$G^*$是唯一的对偶图），度量映射是一个映射$\eta : V(G) \to \mathbb R^3$，使得$\eta(G)$的直径为1，对于每一对顶点$(u,v)$，只要$u\in \tau(v)$，我们就有dist$(\eta(u),\eta(v)) = 1$。如果$\eta$是单射，它被称为度量嵌入。注意，度量嵌入产生了一个Reuleaux多面体。
我们的贡献有两方面：首先，我们证明任何平面的，3连通的，强自对偶的图都有一个度量映射，通过证明直径图（其顶点是$V(G)$，其边是对$(u,v)$，只要$u\in \tau(v)$）的色数最多为4，这意味着存在一个度量映射到四面体。此外，我们使用Lov\'asz邻域复杂定理在代数拓扑中证明直径图的色数正好是4。
其次，我们开发了算法，使我们能够获得所有这样的图，顶点数最多为14。此外，我们为每一个这样的图数值构造度量嵌入。从定理和这个计算证据，我们推测每一个这样的图都可以作为一个Reuleaux多面体在$\mathbb R^3$中实现。
在之前的工作中，第一作者和最后一作者描述了一种从Reuleaux多面体构造常宽体的方法。因此，从本质上讲，我们也构造了数百个新的常宽体的例子。
这与V\'azsonyi的问题，以及Blaschke-Lebesgue的问题有关。

== 问题与动机 ==
作者的研究问题包括：
* 如何确定哪些[[图 (数学)|图]]是[[Reuleaux多面体]]背后的图？
* 什么样的条件是Reuleaux多面体背后的图所必须满足的？
* 如何证明任何[[平面图]]、3-连通、[[强自对偶图]]都有度量映射？
* 如何证明[[直径图]]的色数至多为4？
* 如何开发算法来获得所有这样的图，并数值构造度量嵌入？
* 每一个这样的图是否都可以在R3中实现为Reuleaux多面体？
* 如何从Reuleaux多面体构造出[[恒宽体]]？
* 如何解决[[Vázsonyi问题]]和[[Blaschke-Lebesgue问题]]？

== 背景介绍 ==
这篇文献的背景主要集中在以下几个方面：
# '''Reuleaux多面体的图论基础'''：
#* [[Reuleaux多面体]]是一类特殊的几何形状，由一系列半径为1的球体在三维空间中相交形成。这类多面体在[[凸几何]]和[[离散几何]]中具有重要性。
#* 研究Reuleaux多面体背后的[[图论]]结构，特别是那些满足[[平面性]]、[[3-连通性]]和[[强自对偶性]]的图，对于理解这类多面体的性质至关重要。
# '''图的自对偶性和度量嵌入'''：
#* [[自对偶图]]是一类特殊的图，它们可以通过一个称为对偶的映射与自身形成一一对应关系。这种映射在图论中有着广泛的应用。
#* [[度量嵌入]]是将图的顶点映射到三维空间中，使得满足特定距离条件的映射。这种嵌入可以用来构造Reuleaux多面体。
# '''Reuleaux多面体的构造与分类'''：
#* 构造Reuleaux多面体的一种方法是从一个满足特定条件的自对偶图出发，通过度量嵌入来实现。
#* 对这些图进行分类，并探索它们是否可以实现为Reuleaux多面体，是本文的主要研究目标之一。
# '''与Vázsonyi和Blaschke-Lebesgue问题的关联'''：
#* [[Vázsonyi问题]]涉及到在三维空间中寻找具有特定直径性质的点集，而[[Blaschke-Lebesgue问题]]则关注在常宽凸体类中最小化体积。
#* Reuleaux多面体与这些问题有着密切的联系，因为它们提供了一种构造具有特定几何性质的凸体的方法。
综上所述，这篇文献的背景强调了Reuleaux多面体背后的图论结构的重要性，以及如何通过图的自对偶性和度量嵌入来构造和分类这些多面体。同时，这些研究也与解决Vázsonyi和Blaschke-Lebesgue问题有着直接的联系。

== 章节摘要 ==
这篇论文是关于[[Reuleaux多面体]]背后的图的研究，论文的主要内容可以概括如下：
# 引言
## Reuleaux多边形和多面体的定义：[[Reuleaux多边形]]是半径为r的[[圆]]的交集，其顶点是这些圆的中心。[[Reuleaux多面体]]是三维空间中半径为1的[[球体]]的交集，其边界上的角点与球体中心重合。
## 研究动机：探讨了Reuleaux多面体在[[凸几何]]和[[离散几何]]中的重要性，以及它们与[[常宽体]]的关系。
# Reuleaux多面体背后的图
## 球体多面体的定义：[[球体多面体]]是三维空间中半径为1的球体的交集。
## Reuleaux多面体的性质：讨论了Reuleaux多面体的边界结构，以及如何将其表示为嵌入在边界中的图。
# 反演自对偶图
## 自对偶图的定义：介绍了[[自对偶图]]的概念，以及如何构建自对偶图的对偶图。
## 强反演自对偶图的性质：讨论了[[强反演自对偶图]]必须满足的两个性质。
# 度量嵌入
## 度量映射的定义：定义了强反演自对偶图的[[度量映射]]，即满足特定条件的映射。
## 度量嵌入的存在性：提出了一个猜想，即每个强反演自对偶图都有一个[[度量嵌入]]，并给出了支持该猜想的定理。
# 移除-收缩操作和D(M)的色数
## 移除-收缩操作的定义：介绍了一种操作，通过收缩图的边并删除某些边来简化图。
## D(M)的色数：证明了D(M)的色数恰好为4，这意味着存在一个度量映射到[[正四面体]]的顶点。
# 寻找强反演自对偶图及其度量嵌入
## 算法描述：描述了用于从所有强反演自对偶图中构建Reuleaux多面体的计算[[算法]]。
## 实验结果：提供了计算证据支持每个强反演自对偶图都可以实现为Reuleaux多面体的猜想。
# 结论
## 研究贡献：总结了论文的主要贡献，包括证明了任何平面3-连通强自对偶图都有一个度量映射，以及开发了用于找到这些图的算法。
## 未来工作：提出了未来的研究方向，包括进一步探索Reuleaux多面体的性质和应用。

== 研究方法 ==
这篇论文通过研究[[Reuleaux多面体]]背后的[[图论]]性质，探讨了这些图的性质和它们与三维空间中[[几何体]]的关系。以下是该研究方法论的主要组成部分：
# '''图论分析'''：
#* 研究了Reuleaux多面体背后的图必须是平面的、3-连通的和强自对偶的。
#* 证明了任何满足这些条件的图都有一个度量映射，即存在一个映射到三维空间的点集，使得图的直径为1，并且对于图的任意一对顶点，如果它们是自对偶的，则它们之间的距离为1。
#* 使用了[[色数理论]]，特别是证明了直径图的色数至多为4，这意味着存在一个映射到[[正四面体]]的度量映射。
# '''算法开发'''：
#* 开发了[[算法]]来生成具有特定顶点数的3-连通平面图。
#* 实现了算法来选择强自对偶图，并构建了这些图的直径图。
#* 使用了[[差分进化算法]]来数值构建这些图的度量嵌入。
# '''计算实验'''：
#* 通过计算实验支持了每个这样的图都可以实现为Reuleaux多面体的猜想。
#* 利用计算方法构建了数百个新的[[恒宽体]]的例子。
#* 提供了[[软件工具]]和[[代码]]，用于生成和可视化Reuleaux多面体和[[Meissner多面体]]。
# '''理论证明与猜想'''：
#* 提出了猜想，即每个平面3-连通强自对偶图都可以实现为Reuleaux多面体。
#* 使用了[[代数拓扑]]中的[[Lovász邻域复形定理]]来证明直径图的色数恰好为4。
这篇论文的方法论分析结果表明，通过图论和计算方法可以系统地研究和构建Reuleaux多面体，为理解和探索这类几何体提供了新的视角和工具。

== 研究结论 ==
根据提供的文献内容，这篇论文的主要结论可以概括如下：
# '''Reuleaux多面体背后的图'''：研究了从[[Reuleaux多面体]]中产生的图，这些图必须是平面的、3-连通的和强自对偶的。
## '''度量映射的存在性'''：证明了任何平面的、3-连通的、强自对偶图都有一个度量映射，通过证明直径图的色数最多为4，意味着存在一个到四面体的度量映射。
## '''色数的确定'''：使用[[Lovász]]的邻域复形定理证明了直径图的色数正好是4。
# '''算法开发'''：开发了算法，可以找到多达14个顶点的所有这样的图，并为每个这样的图数值构造度量嵌入。
## '''数值构造'''：为每个这样的图数值构造了Reuleaux多面体。
## '''计算证据'''：提供了计算证据支持每个平面的、3-连通的、强自对偶图都可以实现为Reuleaux多面体的猜想。
# '''球多面体和Reuleaux多面体的性质'''：详细描述了球多面体和Reuleaux多面体的性质，以及它们与图的关系。
## '''球多面体的定义'''：定义了球多面体为半径为1的有限多个球体的交集。
## '''Reuleaux多面体的定义'''：定义了Reuleaux多面体为标准球多面体，其顶点集合与中心点集合重合。
# '''强自对偶图的度量嵌入'''：讨论了强自对偶图的度量嵌入，并提出了猜想，即每个强自对偶图都可以实现为Reuleaux多面体。
## '''猜想2'''：对于每个平面的、3-连通的、强自对偶图G，都存在一个Reuleaux多面体Ω，使得GΩ与G同构。
# '''计算方法和可视化'''：描述了用于从所有强自对偶图构造Reuleaux多面体的计算算法，并提供了可视化结果。
## '''算法步骤'''：包括生成3-连通平面图、选择强自对偶图、在R3中嵌入直径图和从嵌入中创建Meissner或Reuleaux多面体。
## '''软件工具'''：提供了软件工具的链接，用于生成和可视化这些多面体。
这些结论为理解Reuleaux多面体的结构和性质提供了重要的理论基础，并为进一步研究提供了新的工具和方法。

== 术语表 ==
这篇文章的术语表如下：
* [[Reuleaux多面体]]（Reuleaux polyhedra）：Reuleaux多面体是一类特殊的三维形状，由一系列半径为1的球体在三维空间中相交形成，其边界上的角点正是这些球体的中心点。
* [[球多面体]]（Ball polyhedra）：球多面体是三维空间中由有限数量的半径为1的球体相交形成的几何体。
* [[自对偶图]]（Self-dual graph）：如果一个图与其对偶图之间存在一个图同构映射，那么这个图被称为自对偶图。
* [[强自对偶图]]（Strongly involutive self-dual graph）：强自对偶图是一种特殊的自对偶图，其自对偶映射满足特定的性质，如每个顶点不在其自身的对偶集中，且如果一个顶点在另一个顶点的对偶集中，则反之亦然。
* [[度图]]（Diameter graph）：度图是一个图，其顶点是原图的顶点，但其边是原图中对应于自对偶映射关系的顶点对。
* [[度量嵌入]]（Metric embedding）：度量嵌入是指将图的顶点映射到三维空间中，使得满足特定距离条件的嵌入方式。
* [[度量映射]]（Metric mapping）：度量映射是将图的顶点映射到三维空间中的一种方式，其中对偶顶点之间的距离为1，但不需要是单射。
* [[V´azsonyi集合]]（V´azsonyi set）：V´azsonyi集合是一类特殊的有限点集，其直径为1，并且每个点至少属于3个直径。
* [[Meissner多面体]]（Meissner polyhedra）：Meissner多面体是由Reuleaux多面体转换而来的一种具有恒定宽度1的几何体。
* [[球帽]]（Spherical caps）：球帽是球体表面的一部分，通常用于描述Meissner多面体边界的平滑部分。
* [[Blaschke-Lebesgue问题]]（Blaschke-Lebesgue problem）：Blaschke-Lebesgue问题是在恒定宽度的凸体类中最小化体积的问题。
* [[3-连通图]]（3-connected graph）：3-连通图是一种图，其中任意两个顶点之间至少有三条不相交的路径。
* [[图的嵌入]]（Graph embedding）：图的嵌入是指将图的顶点和边映射到一个几何空间中，使得图的结构得以保持。
* [[图的对偶]]（Graph duality）：图的对偶是指构建一个图的对偶图的过程，其中原图的每个面变成对偶图中的一个顶点，原图的每条边对应对偶图中的一条边。
* [[图的自对偶性]]（Graph self-duality）：图的自对偶性是指图与其对偶图之间存在同构映射的性质。
* [[图的直径]]（Graph diameter）：图的直径是指图中任意两个顶点之间的最长最短路径的长度。
* [[图的着色]]（Graph coloring）：图的着色是指将图的顶点或边分配到不同的颜色类别中，以满足特定的条件，如每个颜色类别中的顶点或边不相邻。
* [[图的刚性]]（Graph rigidity）：图的刚性是指图在保持其结构不变的条件下，能够抵抗形状变化的程度。
* [[图的同构]]（Graph isomorphism）：图的同构是指两个图之间存在一种顶点和边一一对应的关系，使得这两个图在结构上是相同的。

== 参考文献 ==
这篇文章的主要参考文献如下：
* [AG11] H. Anciaux and N. Georgiou, On the three-dimensional Blaschke-Lebesgue problem, Proc. Amer. Math. Soc. 139 (2011), 1831–1839.
** 讨论了三维空间中Blaschke-Lebesgue问题的解决方案，为本文提供了理论基础。
* [AR78] L. Asimow and B. Roth, The rigidity of graphs, Transactions of the American Mathematical Society 245 (1978), 279–289.
** 分析了图的刚性，对本文中讨论的Reuleaux多面体的结构稳定性提供了理论支持。
* [BM07] G. Brinkmann and B. D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem 58 (2007), no. 2, 323–357.
** 提供了快速生成平面图的方法，对本文中图的生成和分析有重要贡献。
* [CG83] G. D. Chakerian and H. Groemer, Convex bodies of constant width, Convexity and its Applications, Springer, 1983, pp. 49–96.
** 探讨了常宽凸体的性质，对本文中Reuleaux多面体的几何特性分析有直接影响。
* [KMP10] Y. S. Kupitz, H. Martini, and M. A. Perles, Ball polytopes and the V´azsonyi problem, Acta Mathematica Hungarica 126 (2010), no. 1-2, 99–163.
** 研究了球多面体和V´azsonyi问题，为本文中Reuleaux多面体的数学建模提供了参考。