單位距離圖

在數學中，特別是，單位距離圖（）是指在歐幾里得平面上，將距離恰為1的兩點相互連接而形成的圖。為了將此類圖與允許某些非相鄰頂點對之間距離為一的廣義定義區分開來，此類圖亦可稱為嚴格單位距離圖（）或忠實單位距離圖（）。作為一類，它們可透過來進行特徵化。單位距離圖包含、、以及。廣義彼得森圖則屬於非嚴格單位距離圖。

艾狄胥·帕爾提出的一道問題，稱為單位距離問題（），旨在求解歐幾里得平面上由 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的點對，且常被用來建模無線通訊網路。

舉例
兩個頂點的完全圖是單位距離圖，三個頂點的完全圖（即）亦然，但四個頂點的完全圖則不然。若將三角圖推廣，每個循環圖都是單位距離圖，並由正多邊形實現。兩個有限的單位距離圖，若在單一共用頂點處相連，便會形成另一個單位距離圖，因為其中一個圖可以相對於另一個圖進行旋轉，以避免產生不必要的額外單位距離。透過這種方式連接圖，每個有限樹或皆可實現為單位距離圖。

任何單位距離圖的都會產生另一個單位距離圖；然而，對於某些其他常見的圖積，情況則不然。例如，將應用於任意兩個非空圖時，會產生具有四個頂點的完全圖子圖，而這些子圖並非單位距離圖。的笛卡爾積會形成任意維度的，兩頂點完全圖的笛卡爾積是，而三角圖的笛卡爾積則是 H(d,3)。

其他屬於單位距離圖的特定圖形包括彼得森圖、、輪圖 W_7（唯一同時是單位距離圖的輪圖），以及和（小型四色單位距離圖）。所有廣義彼得森圖，例如圖中所示的，皆為非嚴格單位距離圖。

是單位距離圖的一種特例，其中不存在相交的邊。每個火柴棒圖都是平面圖，但某些本應為平面圖的單位距離圖（例如莫澤紡錘圖）在作為單位距離圖的每種表示法中都存在邊相交的情況。此外，在單位距離圖的語境下，應謹慎使用「平面」一詞，因為有些作者用它來指代定義單位距離的平面，而非指禁止邊相交。是單位距離圖與火柴棒圖中更為特殊的特例，其中每對非相鄰頂點之間的距離均大於一個單位。

性質
邊的數量
提出一道問題：在由 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^{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。這是距離圖與代數數及剛性之間各種關聯的一個實例。作為一個推論，這駁斥了艾狄胥與提出的一項猜想（艾狄胥曾懸賞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，這些邊的數量分別為：

此問題可推廣至 \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 上的歐幾里得規範是特殊的，因為它屬於這個稀疏集合。

禁止子圖
若給定圖 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 的兩個複數根之一，從而產生一個具有四個生成元的無限度單位距離圖。

上色
哈德維格-納爾遜問題涉及單位距離圖的色數，更具體地說，是涉及由歐幾里得平面所有點所構成的無限單位距離圖的色數。根據假設選擇公理成立的，這等同於探討有限單位距離圖的最大色數。存在某些單位距離圖，其任何正確著色皆需五種顏色；且所有單位距離圖最多只需七種顏色即可完成著色。

回答艾狄胥·帕爾的另一個問題：無三角形的單位距離圖確實可能需要四種顏色。

枚舉
具有 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^ 為緩慢增長的迭代對數函數

判定給定圖是否為平面上的（嚴格或非嚴格）單位距離圖屬於NP困難問題——更具體地說，該問題對於而言是完全的。此外，判定平面單位距離圖是否具有哈密頓環，即使該圖的所有頂點座標皆為已知的整數，亦屬於NP完全問題。

參考資料
備註
來源
*
*
*
*
*
*
*
*
*
*
*, as cited by
*
*
*
*
*
*, as cited by
*; see in particular [https://books.google.com/books?id=tmORL-UYOyEC&pg=PA475 p. 475]
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*

外部連結
*
*