algorithm - 如何计算循环图的密度？

Question

我正在寻找有向循环图的密度。

根据 Wikipedia ,

For undirected simple graphs, the graph density is defined as:

2 * |E| / (|V| * (|V| − 1))

For directed simple graphs, the graph density is defined as:

|E| / (|V| * (|V| − 1))

但我随后继续阅读 simple graphs 的定义:

"A simple graph, as opposed to a multigraph, is an undirected graph in which both multiple edges and loops are disallowed."

我很困惑，因为另一篇文章提到了“有向”和“无向”的简单图。现在简单的图只能是无向的？它还指出简单图不能有循环，所以我不确定我是否能够在我的循环图上使用这些公式中的任何一个。

我继续阅读有关多重图的内容，但没有提到计算它们的密度。
对于具有循环的图形，密度不是人们会关心的东西吗？

在第一篇文章中指出:

"the maximal density is 1 (for complete graphs)"

看起来完全图是多重图的特殊版本，所以我认为计算密度应该是有意义的。

我使用什么公式？

Answer 1

我理解你的困惑，但其实并不复杂。 Yuo 只是从不同的来源选择了不一致的定义。

对我来说，简单图的概念与有向图或无向图没有任何关系(或几乎没有关系)(我在该领域攻读博士学位)。

Undirected 表示边没有起点或终点。它是顶点 {a,b} 的 2 组(或多重集)(与边 {b,a} 无法区分，可能包含两次相同的顶点 {a,a}，这称为 循环.

定向 表示边(在这种情况下有时也称为弧)具有源顶点和目标顶点。这意味着它是一个 2 元组 (a,b)，并且 (a,b) 和 (b,a) 之间存在差异。同样，(a,a) 将是一个循环。

简单意味着 1.没有循环(即使有时定义不同) 2. 没有边缘出现两次或更多次(这将是一个多重图)

让我们暂时忘记简单图应该是无向的说法。

请注意，2. 表示如果无向图中存在边 {a,b}，则它可能不包含边 {b,a}，因为那是同一条边。在有向简单图中，仍然可能有 (a,b) 和 (b,a)。

现在，密度 是边数除以最大边数。在多重图中，没有最大边数，因此，您找到的定义仅适用于简单图。

简单无向图最多有 |V|(|V|-1)/2 条边，简单有向图最多有 |V|(|V|-1) 条边。

令人困惑的是简单图的定义是无向的。算了吧。在图论中，不同来源仍然存在不一致的概念。我不希望将无向性包含在简单性中，因为它混合了概念并且让您没有明确的有向简单图措辞。