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多面体的构造与分类：
- 构造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多面体的猜想。
- 利用计算方法构建了数百个新的恒宽体的例子。
- 提供了软件工具和代码，用于生成和可视化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多面体的数学建模提供了参考。