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

Question

this link上显示的图表“具有 6 个顶点和 7 个边的图，其中最左侧的第 6 个顶点是叶顶点或悬垂顶点。”有直径 4 吗？对还是错？

定义是

The diameter of a graph is the maximum eccentricity of any vertex in the graph. That is, it is the greatest distance between any pair of vertices. To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.

Diameter, D, of a network having N nodes is defined as the maximum shortest paths between any two nodes in the network

Diameter, D, of a network having N nodes is defined as the longest path, p, of the shortest paths between any two nodes D ¼ max (minp[pij length( p)). In this equation, pij is the length of the path between nodes i and j and length (p) is a procedure that returns the length of the path, p. For example, the diameter of a 4 4 Mesh D ¼ 6.

Answer 1

维基百科示例

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



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

网格示例

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

Diameter D of a network is defined as the longest path of the shortest paths between any two nodes. For example, the diameter of a 4x4 mesh D = 6

我们来看看 4x4 mesh例子:

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

The length of the "longest shortest path" between any two graph vertices of a graph.

Graph and Digraph Glossary - cudenver.edu

Diameter: The diameter of a graph is the length of the longest chain you are forced to use to get from one vertex to another in that graph. You can find the diameter of a graph by finding the distance between every pair of vertices and taking the maximum of those distances.

也可以看看

Computing Distances and Diameter

有关于加权图的例子