圖距離矩陣

圖距離矩陣，有時也稱為所有頂點對最短路徑矩陣，是包含從頂點 到頂點 的所有圖距離的方陣 。圖的距離矩陣由 Graham 和 Pollak (1971) 引入。

一個（連通）圖中所有距離的平均值被稱為該圖的平均距離。所有距離矩陣元素的最大值被稱為圖直徑。

圖距離矩陣的特徵多項式被稱為距離多項式。

圖距離矩陣可以在 Wolfram 語言 中使用內建函式計算：GraphDistanceMatrix[g]，並且可以使用以下方法獲得許多命名圖的預計算距離矩陣：GraphData[graph,"DistanceMatrix"].

對於一個有 個頂點的連通圖，線性方程組

(1)

其中 是距離矩陣， 是由 個 1 組成的向量，對於“大多數”圖往往有一個實數解 (Steinerberger 2022)。例外情況包括完全 部圖 和 ，“雙吃豆人圖”， 騎士圖，以及 14 節點 三次圖 #52 和 11 節點 四次圖 #18（在編號中GraphData）。在 , 2, ... 個節點上，上述方程無解的連通圖的數量分別為 1, 0, 0, 0, 0, 0, 2, 14, 398, 23923, ... (OEIS A354465)。Dudarov et al. (2023) 證明了對於所有 ，這種圖都存在。

上面說明了前幾個“一向量不在距離矩陣影像圖”也是 k 樹（這種情況發生在 , 7 和 8 個節點時）。8 節點圖 #1 和 #2 是 2 樹，而 8 節點圖 #13 是 4 樹 (E. Weisstein, 1 月 18 日, 2024 年)。

與最大特徵值相關的具有非負項的實特徵向量 （根據 Perron-Frobenius 定理 保證存在）在 內積 滿足的意義上幾乎是常數：

(2)

其中 是 範數 (Steinerberger 2022)。然而，對於數千個連通圖的距離矩陣的 Perron-Frobenius 特徵向量，在GraphData給出的 的平均值接近 ，而不是 。Steinerberger (2023) 指出，這種情況可能成立的條件顯然是一個懸而未決的問題。然而，某些族的極限情況的精確值是已知的，例如，

(3)

對於路徑圖 ，其中 是 的正根 (Ruzieh and Powers 1990, Steinerberger 2023)，以及

(4)

對於 太陽圖 (Steinerberger 2023)。這些考慮與圖曲率的定義有關。