为什么 n 个顶点和 m 条边的完整有向图 G 有 m = n(n-1) 条边。但是我尝试了很多例子来证明这个陈述是错误的，这将是 n(n-1)/2 但是我们的教授给出了这个陈述的真实性。谁能给我解释一下这个说法的正确性？
最佳答案
我想你还没有完全理解有向图和无向图的区别。
请记住，在无向图中，边的方向并不重要。 但在有向图中，边的方向很重要。
打个比方，假设两个城市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)。
关于algorithm - 有向图中顶点和边的关系，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49768543/