graph-theory - 如何计算具有 5 个顶点的图形的直径？

Question

我想计算一个有 5 个顶点的图的直径。我怎样才能做到这一点？例如，如果我有一个包含 5 个顶点和 8 个边的图。

标签： graph-theory

Answer 1

正如维基中所说：

要找到图的直径，首先要找到每对顶点之间的最短路径。这些路径的最大长度是图形的直径

关于您关于 G 有 5 个节点和 8 个顶点的问题：

假设每条边的权重为 1。请注意，最大值 |E| 对于 DAG 是 |V|*(|V|-1) /2 -> 所以在你的情况下是 10 (5*4/2)。如果图中有 10 条边，则直径为 1（每对之间的最短路径为 1，因为每个节点都连接到所有其他节点）。在您的情况下，有 8 个边，因此它们有 2 个未直接连接的顶点 -> 使直径最小为 2。

让我们看一下具有 10 条边的 5 个节点的完整图：

请注意，为了增加 2 个节点之间的路径，让我们首先删除它们的连接边。但是，在该图中的 2 个节点之间，我们还有 3 条距离为 2 的路径。因此，如果您删除 2 条边，您仍然会有 2 条距离为 2 的路径 -> 当 |V|= 时 G(V,E) 的直径5 和 |E|=8 是 2