网络直径是什么意思？

Question

上图所示此连结的的" 的曲线图具有6个顶点和7层的边缘,其中所述顶点在最左的无6是叶顶点或侧链顶点. "具有直径为4？对还是错？

定义是

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

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

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

Answer 1

维基百科示例

根据定义,看起来直径是3.

最长的最短路径具有3个边缘的长度,例如在6-1和之间6-2.

网格示例

这是你的第二个定义,有一些印刷修正,所以它是有道理的:

D网络直径定义为任意两个节点之间最短路径的最长路径.例如,4×4网格的直径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/Graph Diameter

  图形的任意两个图形顶点之间的"最长最短路径"的长度.

• 图形和图形词汇表 - cudenver.edu

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

也可以看看

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