DAG中可以有多少條邊？

在有n個頂點的有向無環圖中，有向邊的最大可能數是多少？DAG中可以有多少條邊？

2012-07-28 user1559262

這個問題是關閉堆棧溢出主題。您可以嘗試http://math.stackexchange.com/，歡迎所有級別的數學問題。 – 2012-07-28 07:19:50

更何況，這聽起來像一個家庭作業問題。而且我採取了誘餌： -/ – 2012-07-28 07:21:10

此外，它是[我如何證明最大邊數？]的副本（http://math.stackexchange.com/questions/61579/how-can-i-prove-最大數量的邊緣） – 2012-07-28 07:25:19

假設有N個頂點/節點，讓我們探索構建一個具有最大邊緣的DAG。考慮任何給定節點，比如N1。它在這個早期階段可以指向的最大節點數或邊數是N-1。我們選擇第二個節點N2：它可以指向除自身和N1之外的所有節點 - 這是N-2個附加邊。繼續剩下的節點，每個節點可以指向比之前的節點更少的邊。最後一個節點可以指向0個其他節點。

薩姆所有邊緣的：（N-1）+（N-2）+ ... + 1 + 0 ==（N-1）（N）/ 2

來源

2012-07-28 07:19:51

非常感謝您的回答。 – user1559262 2012-07-28 07:32:04

嗯，[這]（http://stackoverflow.com/questions/5058406/what-is-the-maximum-number-of-ed-in-a-directed-graph-with-n-nodes）似乎爭論與答案。 – 2012-09-13 03:06:15

@RealzSlaw區別在於DAG是「非循環」的;您提到的帖子一般會討論有向圖。 – 2012-09-14 04:24:03

DAG中可以有多少條邊？

回答

相關問題