logo标签列表

网络直径指的是在网络中从最远距离的两个节点之间的最短路径的长度。

graph-theoryterminologyshortest-path
30
在此链接上显示的“一个具有6个顶点和7条边的图形，在最左边的第6个顶点是叶子节点或挂件节点。”的图表直径是否为4？对还是错？
定义如下：

图的直径是该图中任意一个顶点到其他所有顶点最长路径中的最大值。要找到一个图的直径，首先找到每对顶点之间的最短路径，然后找到这些路径中的最长路径，它就是图的直径。

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

具有N个节点的网络的直径D被定义为最短路径的最长路径p，其中pij是节点i和j之间的路径长度，length（p）是返回路径p的长度的过程。例如，4x4网格的直径D=6。

答案是可能正确也可能错误，因为从图表中未提供足够的信息来确定该图的直径。
2
你从哪里得到第二个定义的？能否请您正确引用它，包括所有符号？ - polygenelubricants
1个回答
43

维基百科的例子

根据定义，我认为直径是3。

alt text

最长的最短路径长度为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。

参考资料

另请参阅

5
假设每条边的权重都为1。 - fmark
1
每个边缘的权重都是预先定义好的，它是图的一部分。 - blwy10
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接