有向圖中最大邊數是多少，沒有平行邊？

Question

我知道這可能類似於this question，但我想知道如果允許並行邊緣（又稱多邊）是而不是，那麼圖中邊的最大數目是多少。我知道給定V頂點的最大邊數爲V * (V - 1)。

Answer 1

你說：

「我知道，邊緣的最大數量，鑑於第五頂點，將V *（V - 1）。」

但是，這不是一個沒有指示的圖。給定n個策略，它實際上是nC2 = n(n-1)/2。我想，但我不確定，這是你在找什麼。

如果圖表被引導（即Va→Vb與Vb→Va不是同一條線），那麼它會升至您引用的n * (n-1)。

如果圖形允許您從節點到其自身的邊緣，則總數爲n^2。

Answer 2

如果平行的邊緣沒有以允許作圖器（即，如果邊緣a -> b存在，那麼b - > a是不允許的），邊緣的最大數目將是簡單VC2或(V*(V-1))/2