此有向圖中有多少個3邊循環？

Question

如何計算n個節點和n *（n-1）/ 2個有向邊強連通圖中有多少個3邊循環？

Answer 1

您正在查找的數字不是一個常數，它取決於如何放置n(n-1)/2邊緣，因此無法以分析方式計算它。例如，圖G1=({1,2,3,4}, {(1,2), (2,3), (3,4}, (4,1), (2,1), (4,3)}具有n = 4節點和n(n-1)/2 = 6邊，但不包含3邊循環。相反，圖表G2=({1,2,3,4}, {(1,2), (2,3), (3,4), (4,1), (3,1), (4,2)}有兩個3邊沿週期。這個想法可以很容易地推廣到更大的值n，此外，如果您不允許「反向邊緣」（例如，您不能在G1中同時有(1,2)和(2,1)），它仍然成立。這個例子有更多的涉及，你實際上需要5個節點。

因此，尋找計算特定圖的3邊循環數的算法是合理的。對於G=(V,E)蠻力算法會是這樣的：

count = 0 
for n1 in V: 
    for n2 in V: 
    for n3 in V: 
     if E(n1, n2) and E(n2, n3) and E(n3, n1): 
     count +=1 
return(count/3) # because each triangle is counted 3 times 

，如果你有這樣的節點可以優化和邊緣索引，但我想這超出了你的問題的範圍。我希望我能正確理解你的問題，我的答案是有幫助的。