2017-04-05 111 views
0

給定正整數n,通過爲圖生成鄰接矩陣 來生成具有n個頂點的簡單定向圖,使得具有n個頂點的所有簡單有向圖同樣可能被生成。圖的鄰接矩陣實現

什麼是「所有簡單有向圖與n 頂點同樣可能產生」的意思是?

回答

1

國際海事組織,這個問題是非常糟糕的措辭。如果你知道答案,很明顯,如果你不知道,你就無法理解這個問題。本質上,問題要求如下:

1)您正在尋找一些配方來生成具有規定數量的頂點/節點的有向圖。您應該指定圖形的方式是方矩陣,即鄰接矩陣A,其中A[i,j] = 1表示是從頂點/節點ij的連接。

2)該配方應包括一些初始化步驟,其涉及的隨機數,使得你最終與任何特定圖形(例如全連通圖)概率是相同的爲大小爲n的所有可能的圖表。