有向图中顶点与边的关系

Question

为什么在 n 个顶点和 m 条边上的完整有向图 G 有 m = n(n-1) 条边。但是我尝试了很多例子来证明这个陈述是错误的，这将是 n(n-1)/2 但是我们的教授对这个陈述给出了正确的答案。有人可以向我解释这种说法的正确性吗？

Answer 1

我认为您还没有完全理解有向图和无向图之间的区别。

请记住，在无向图中，边的方向无关紧要。但在有向图中，边的方向很重要。

打个比方，假设 A 和 B 两个城市由图的两个节点表示，连接它们的路径表示边。现在如果边缘是无向的，你可以从 A 到 B，反之亦然。但是，如果它是定向的，则意味着这是一条单向路，您只能从 A 到 B，反之亦然（取决于方向）。

现在回答你的问题，在一个无向图中，边的总数是

C(n,2) = (n*(n-1))/2。

但是在有 n 个节点的有向图中，每条边都可以加倍。即，一个从 A 到 B，另一个从 B 到 A。

因此，边的总数 = 2*C(n,2)

这转化为n*(n-1)。