网络直径是什么意思？

上图所示这个链接 http://en.wikipedia.org/wiki/Vertex_%28graph_theory%29的 ”具有 6 个顶点和 7 个边的图，其中最左侧的 6 号顶点是叶顶点或下垂顶点。“有直径4吗？对还是错？

定义是

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

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

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

维基百科的例子

根据定义，直径对我来说似乎是 3。

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

网格示例

这是您的第二个定义，经过一些排版更正，使其有意义：

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

我们来看看4x4mesh http://en.wikipedia.org/wiki/Lattice_graph例子：

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

最长最短路径的长度为 6 条边，即A-P and M-D.

参考

• Mathworld - Wolfram/图形直径 http://mathworld.wolfram.com/GraphDiameter.html

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

• 图和有向图术语表 - cudenver.edu http://www-math.ucdenver.edu/~wcherowi/courses/m4408/glossary.htm

  Diameter http://www-math.ucdenver.edu/~wcherowi/courses/m4408/glossary.htm#Diameter：图的直径是从该图中的一个顶点到另一个顶点被迫使用的最长链的长度。您可以通过查找每对顶点之间的距离并取这些距离的最大值来找到图的直径。

See also

• Computing Distances and Diameter http://web.archive.org/web/20080330235019/http://www.cs.auckland.ac.nz/~ute/220ft/graphalg/node19.html
  • 有加权图示例