graph-theory - 网络的直径是什么意思？

Question

“ A graph with 6 vertes and 7 edges where the vertex no 6 on the far-left is a leaf vertex or a pendant vertex. ”的链接上显示的图有 DIAMETER 4？对还是错？

定义是

图的直径是图中任意顶点的最大偏心率。也就是说，它是任何一对顶点之间的最大距离。要找到图的直径，首先要找到每对顶点之间的最短路径。这些路径中任何一条的最大长度是图形的直径。

具有 N 个节点的网络的直径 D 定义为网络中任意两个节点之间的最大最短路径

具有 N 个节点的网络的直径 D 定义为任意两个节点之间的最短路径 D ¼ max (minp[pij length( p)) 中的最长路径 p。在这个等式中，pij 是节点 i 和 j 之间的路径长度，长度 (p) 是返回路径长度 p 的过程。例如，4 4 Mesh D ¼ 6 的直径。

Answer 1

维基百科示例

根据定义，看起来直径对我来说是 3。

最长的最短路径的长度为 3 条边，例如在6-1和之间6-2。

---

网格示例

这是您的第二个定义，并进行了一些排版更正，以使其有意义：

网络的直径D定义为任意两个节点之间最短路径中最长的路径。例如，4x4 网格的直径 D = 6

让我们看一下 4x4网格示例：

A---B---C---D
|   |   |   |
E---F---G---H
|   |   |   |
I---J---K---L
|   |   |   |
M---N---O---P

最长最短路径的长度为 6 条边，即在A-P和之间M-D。

参考

• Mathworld - Wolfram/图形直径

  图的任意两个图顶点之间的“最长最短路径”的长度。

• 图和有向图词汇表 - cudenver.edu

  直径：图的直径是您在该图中从一个顶点到另一个顶点时被迫使用的最长链的长度。您可以通过找到每对顶点之间的距离并取这些距离中的最大值来找到图形的直径。

也可以看看

• 计算距离和直径
  • 有关于加权图的例子