单位距离图

<image>

在数学中，特别是几何图论领域，单位距离图（Unit distance graph）是指在欧几里得平面上，将距离恰为1的两点相互连接而形成的图。为了将此类图与允许某些非相邻顶点对之间距离为一的广义定义区分开来，此类图亦可称为严格单位距离图（Strict unit distance graph）或忠实单位距离图（Faithful unit distance graph）。作为一类遗传性质，它们可透过禁止子图刻画来进行特征化。单位距离图包含仙人掌图、火柴棒图、便士图以及超立方体图。广义彼得森图则属于非严格单位距离图。

艾狄胥·帕尔提出的一道问题，称为单位距离问题（Unit distance problem），旨在求解欧几里得平面上由 $n$ 个点所决定的单位距离对的最大可能数量；等价地，它要求求解具有 $n$ 个顶点的单位距离图中边的最大数量。目前已知的最佳上界为 $O(n^{4/3})$。目前已知的最佳下界为 $\Omega(n^{1.014})$（当 $n$ 足够大时）。为T个单位距离图着色所需的颜色数目前亦未知；在平面上的等效哈德维格-纳尔逊问题中，某些单位距离图需要五种颜色，且每个单位距离图皆可用七种颜色着色。对于每个代数数 $\alpha$，都存在一个具有两个顶点的单位距离图，且这两顶点之间的距离必须为 $\alpha$。根据贝克曼-夸尔斯定理，唯一能保持所有单位距离图不变的平面变换是欧几里得平面等距变换。

若已知其顶点，便能高效地构建一个单位距离图。找出所有单位距离在模式匹配领域具有应用价值，这可作为寻找较大模式之全等副本的第一步。然而，判定给定图是否能表示为单位距离图属于NP困难问题，更具体地说，在实数的存在论下，此问题是完全问题。

## 定义

平面中一组点的单位距离图，是指以这些点为顶点、且当两个顶点的欧几里得距离恰为1时即在两者之间存在边的无向图。若能为某个抽象图的顶点在平面上找到不同的位置，使得其边长为单位长度，且所有非相邻的顶点对之间距离均不为单位长度，则该抽象图被称为单位距离图。若能满足此条件，该抽象图即与所选位置的单位距离图同构。此外，部分文献采用更宽泛的定义，允许非相邻的顶点对之间存在单位距离。由此产生的图即为（如本文所定义之）单位距离图的子图。当术语可能产生歧义时，那些非边之间必须保持非单位距离的图，可称为严格单位距离图（Strict unit distance graph）或忠实单位距离图（Faithful unit distance graph）。单位距离图的子图，等同于仅使用一种边长即可在平面上绘制的图。为简明起见，本文将其称为“非严格单位距离图”。

单位距离图不应与单位圆盘图混淆，后者连接距离小于或等于1的点对，且常被用来建模无线通讯网络。

## 举例

两个顶点的完全图是单位距离图，三个顶点的完全图（即三角图）亦然，但四个顶点的完全图则不然。若将三角图推广，每个循环图都是单位距离图，并由正多边形实现。两个有限的单位距离图，若在单一共用顶点处相连，便会形成另一个单位距离图，因为其中一个图可以相对于另一个图进行旋转，以避免产生不必要的额外单位距离。透过这种方式连接图，每个有限树或仙人掌图皆可实现为单位距离图。

超立方体图 $Q_4$ 拥有16个顶点和32个单位距离

汉明图 $H(3,3)$ 拥有 27 个顶点和 81 个单位距离任何单位距离图的图的笛卡尔积都会产生另一个单位距离图；然而，对于某些其他常见的图积，情况则不然。例如，将图的强积应用于任意两个非空图时，会产生具有四个顶点的完全图子图，而这些子图并非单位距离图。路径图的笛卡尔积会形成任意维度的格子图，两顶点完全图的笛卡尔积是超立方体图，而三角图的笛卡尔积则是汉明图 $H(d,3)$。

其他属于单位距离图的特定图形包括彼得森图、希伍德图、轮图 $W_7$（唯一同时是单位距离图的轮图），以及莫泽纺锤图和格伦布图（小型四色单位距离图）。所有广义彼得森图，例如图中所示的莫比乌斯-康托尔图，皆为非严格单位距离图。

火柴棒图是单位距离图的一种特例，其中不存在相交的边。每个火柴棒图都是平面图，但某些本应为平面图的单位距离图（例如莫泽纺锤图）在作为单位距离图的每种表示法中都存在边相交的情况。此外，在单位距离图的语境下，应谨慎使用“平面”一词，因为有些作者用它来指代定义单位距离的平面，而非指禁止边相交。便士图是单位距离图与火柴棒图中更为特殊的特例，其中每对非相邻顶点之间的距离均大于一个单位。

## 性质

### 边的数量

一组 $n$ 个点能确定多少个单位距离？

提出一道问题：在由 $n$ 个点组成的集合中，有多少对点之间的距离为单位距离？用图论的术语来说，这个问题探讨了单位距离图的密度能有多高，而艾狄胥关于此问题的论文，是极值图论领域最早的研究成果之一。

设此数为 $g(n)$。透过超立方图与汉明图的构建，可证明 $g(n) = \Omega(n\log n)$。透过考量在间距经过精心选择的正方形网格中的点，艾狄胥发现了更优的下界 $g(n) > n^{1 + c/\log\log n}$，其中 $c > 0$ 为某个常数。该论文亦建立了上界 $g(n) < n^{3/2}$。

由于上界为 $n^{3/2}$，而下界 $n^{1 + c/\log\log n}$ 会被任何常数 $\epsilon > 0$ 下的 $n^{1+\epsilon}$ 所支配，艾狄胥推测，对于任何 $\epsilon > 0,$，$g(n) = O(n^{1+\epsilon})$。针对此猜想的证明或反证，他最初悬赏300美元，随后将奖金提高至500美元。2026年5月，OpenAI开发的一款人工智能模型透过一种构建方式，证实了此猜想不成立，该构建方式满足 $g(n) \geq \Omega(n^{1+\epsilon})$，其中 $\epsilon \approx 6.24\times 10^{-38}$。此构建方式运用了代数数论，具体而言是戈洛德-沙法列维奇定理。此界限随后由威尔·索温迅速改进为 $\epsilon > 0.014$。这是距离图与代数数及刚性之间各种关联的一个实例。作为一个推论，这驳斥了艾狄胥与彼得·C·费什伯恩提出的一项猜想（艾狄胥曾悬赏500美元征求证明，但驳斥该猜想仅悬赏50美元）。

另一方面，此问题最广为人知的上界为

$$g(n) \leq \sqrt[3]{\frac{29n^4}{4}}\approx 1.936n^{4/3}$$

这个上界可视为计算点与单位圆之间的交点数，且与交点数不等式以及关于点与直线之间交点数的塞梅雷迪–特罗特定理密切相关。

1959年，艾狄胥与李奥·莫泽探讨了此问题在凸多边形顶点上的特例。在此情况下，单位距离的最大数量至多为 $n\log_2 n+4n$。目前仅知其线性下界为 $2n-7$。

当 $n$ 取较小值时，已知可能边的精确最大数量。对于 $n=2,3,4,\dots$，这些边的数量分别为：

1, 3, 5, 7, 9, 12, 14, 18, 20, 23, 27, 30, 33, 37, 41, 43, 46, 50, 54, 57 A186705

此问题可推广至 $\R^3, \R^4, \dots.$ 上的欧几里得范数。对于 $\R^d$ 且 $d \geq 4,$ 为偶数时，艾狄胥证明了 $g(n) = \tfrac 12 (1 - 1/\lfloor d/2 \rfloor) n^2 + \Theta(n)$。对于奇数 $d \geq 5$ 的 $\R^d$，艾狄胥和保奇·亚诺什证明了 $g(n) = \tfrac 12 (1 - 1/\lfloor d/2 \rfloor) n^2 + \Theta(n^{4/3})$。关于 $\R^3$ 的情况仍是未解问题。目前最佳结果为：下界为 $g(n) \geq \Omega(n^{4/3} \log\log n)$，上界则为对于任意 $\epsilon$，有 $g(n) \leq O(n^{295/197 + \epsilon})$。

此问题可推广至任意维度实数空间 $\R^d$ 上的任意范数。给定一范数 $\|\cdot \|,$，据此定义 $g_{\|\cdot \|}(n)$。此问题已在一般情况下得到解决。具体而言，对于任意整数 $d\geq 2,$，对几乎所有范数 $\|\cdot \|,$ 而言。

$$\frac{d-1-o(1)}{2} n\log_2 n \leq g_{\|\cdot\|}(n) \leq \frac d2 n\log_2 n$$

也就是说，在将 $\R^d$ 视为以规范单位球之间的豪斯多夫距离为度量的度量空间时，所有规范中违反此条件的规范所构成的集合是稀疏的。从这个意义上来说，在 $\R^2$ 上的欧几里得规范是特殊的，因为它属于这个稀疏集合。

另一方面，Valtr 在 $\R^2$ 上构建了一种度量，该度量与欧几里得度量相似，但满足 $g(n) \geq \Omega(n^{4/3})$，这暗示对于原问题，若要改善 $g(n) \leq O(n^{4/3})$ 的结果，将需要特别利用欧几里得范数的某些精妙性质。

### 禁止子图

若给定图 $G$ 不是非严格单位距离图，则其任何超图 $H$ 亦非严格单位距离图。对于严格单位距离图，同样的思路亦适用，但需使用导出子图的概念，即由给定顶点子集中所有顶点对之间的边所构成的子图。若 $G$ 不是严格单位距离图，则任何以 $G$ 为导出子图的 $H$ 亦非如此。由于子图及其超图是否为单位距离图之间存在此种关联，因此可透过其禁止子图刻画来描述单位距离图。这些是给定类型中不属于单位距离图的最小图。它们可用于判定给定图 $G$ 是否属于任一类型的单位距离图。若且仅若 $G$ 不是非严格单位距离图之禁用图的超图，则 $G$ 为非严格单位距离图。若且仅若 $G$ 不是严格单位距离图之禁用图的导出超图，则 $G$ 为严格单位距离图。

无论是对非严格单位距离图还是严格单位距离图而言，其禁止图均包含完全图 $K_4$ 及完全二分图 $K_{2,3}$。对于 $K_{2,3}$，无论将此图中两顶点一侧的顶点放置于何处，距离它们一单位距离内最多只有两个位置可用来放置其余三个顶点，因此不可能将这三个顶点全都放置在不同的点上。在顶点数不超过五个的非严格单位距离图中，这仅是仅有的两个禁止图；在顶点数不超过七个的图中，有六个禁止图，而在顶点数不超过九个的图中，则有74个禁止图。由于将两个单位距离图（或其子图）在某个顶点处进行拼接，会产生严格（或非严格）的单位距离图，因此每个禁止图都是双连通图，即无法透过此拼接过程构成的图。

轮图 $W_7$ 可实现为一个严格单位距离图，其中六个顶点构成一个单位正六边形，第七个顶点位于该六边形的中心。若从中心顶点移除一条边，所得到的子图虽然边长仍为单位长度，但已不再是严格单位距离图。其顶点以正六边形排列，是唯一一种（在全等关系下）能将顶点置于不同位置且相邻顶点间距为单位距离的配置方式，且此配置亦使缺失边的两端点间距为单位距离。因此，它属于严格单位距离图的禁止图，但并非非严格单位距离图的六种禁止图之一。其他既非严格单位距离图亦非非严格单位距离图的例子，包括从 $W_7$ 移除一条外边所形成的图，以及从三角柱中移除其中一个三角形的一条边所形成的六顶点图。

### 代数数与刚性

对于每个代数数 $\alpha$，皆可构建一个单位距离图 $G$，使得在 $G$ 的所有单位距离表示中，总存在某一对顶点之间的距离为 $\alpha$。此结果暗示了贝克曼-夸尔斯定理的有限版本：对于任意两点 $p$ 和 $q$，若彼此距离为 $\alpha$，则存在一个包含 $p$ 和 $q$ 的有限刚性单位距离图，使得任何能保持该图中单位距离的平面变换，亦能保持 $p$ 与 $q$ 之间的距离。贝克曼-夸尔斯定理的全文指出，欧几里得平面（或更高维度的欧几里得空间）中，唯一能保持单位距离的变换是等距同构。等价地，对于由平面中所有点生成的无限单位距离图，所有图自同构都保持平面中的所有距离，而不仅仅是单位距离。

若 $\alpha$ 是一个模为1的代数数，且非单位根，则 $\alpha$ 的幂次之整数组合，构成复数加法群的一个有限生成群，其单位距离图的度数为无限大。例如，可将 $\alpha$ 选为多项式 $z^4-z^3-z^2-z+1$ 的两个复数根之一，从而产生一个具有四个生成元的无限度单位距离图。

### 上色

哈德维格-纳尔逊问题涉及单位距离图的色数，更具体地说，是涉及由欧几里得平面所有点所构成的无限单位距离图的色数。根据假设选择公理成立的德布鲁因-艾狄胥定理 (图论)，这等同于探讨有限单位距离图的最大色数。存在某些单位距离图，其任何正确着色皆需五种颜色；且所有单位距离图最多只需七种颜色即可完成着色。

<image>

回答艾狄胥·帕尔的另一个问题：无三角形的单位距离图确实可能需要四种颜色。

### 枚举

具有 $n\ge 4$ 个标记顶点的严格单位距离图的数量，至多为

$$\binom{n(n-1)}{2n}=O\left(2^{\bigl(4+o(1)\bigr)n\log_2 n}\right),$$

如使用大O符号和小o符号所表示。

## 推广至更高维度

单位距离图的定义自然可以推广至任何更高维度的欧几里得空间。在三维空间中，由 $n$ 个点构成的单位距离图最多有 $n^{3/2}\beta(n)$ 条边，其中 $\beta$ 是一个与阿克曼函数倒数相关的极缓增长函数。此结果亦导出了三维相对邻域图边数的类似上界。在四维或更高维度中，任何完全二分图皆为单位距离图，其可透过将点置于两个具有共同中心的垂直圆上来实现，因此单位距离图可以是稠密图。单位距离图的计数公式可推广至更高维度，并显示在四维或更高维度中，严格单位距离图的数量远大于单位距离图的子图数量。

任何有限图皆可在足够高的维度中，作为单位距离图进行嵌入。某些图在作为非严格单位距离图与严格单位距离图进行嵌入时，所需的维度可能大不相同。例如，具有 $2n$ 个顶点的冠状图可在四维空间中作为非严格单位距离图进行嵌入（即其所有边长皆为单位长度）。然而，若要将其嵌入为严格单位距离图（即其边是唯一的单位距离对），则至少需要 $n-2$ 维度。将任意给定图实现为严格单位距离图所需的维度，至多为其最大度数的两倍。

## 计算复杂度

根据点集构建单位距离图，是其他算法在较大的点集中寻找某种模式之全等副本时的重要步骤。这些算法利用此构建方法，搜寻模式中某个距离存在的候选位置，然后针对每个候选位置，使用其他方法来验证模式的其余部分。提出的一种方法可应用于此问题，从而得到一种算法，能在时间复杂度 $n^{4/3}2^{O(\log^* n)}$ 内求出平面点集的单位距离图，其中 $\log^*$ 为缓慢增长的迭代对数函数

$O(n^{4/3})$

判定给定图是否为平面上的（严格或非严格）单位距离图属于NP困难问题——更具体地说，该问题对于实数的存在论而言是完全的。此外，判定平面单位距离图是否具有哈密顿环，即使该图的所有顶点座标皆为已知的整数，亦属于NP完全问题。