图距离矩阵

图距离矩阵，有时也称为所有顶点对最短路径矩阵，是包含从顶点 到顶点 的所有图距离的方阵 。图的距离矩阵由 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)。这些考虑与图曲率的定义有关。