有N個頂點和E邊的圖有多少個不同的鄰接矩陣？

我的看法：

假設它是一個無向圖;

形容詞中每一行的尺寸。無論邊的數量如何，頂點的矩陣都是N.因此，第一行可能的排列數= N !.

第二行的總排列=（N-1）！因爲一個細胞在第一行已經被照顧。同樣，第三行=（N-2）！。。。對於第N行= 1

總排列= N！ + N-1！+ ... + 1！

如果考慮無向或有向圖將產生不同的結果，我很困惑。如果我們考慮圖表被引導，答案會如何改變？

我會試一試，但如果不清楚，請提問。因爲它是N !,我們假設一個無向圖。

對於具有N個頂點的圖，它將用一個NxN矩陣（二維數組）表示，每個值都是0（邊不存在）或1（邊存在）。在這裏，我們沒有考慮邊緣上的其他權重。

然後，我們考慮所有可能的任務。如果第一行有N個不同的選擇，則第二行必須有N-1個選擇（因爲我們已經知道邊緣1,2），依此類推。 N *（N-1）*（N-2）* ... * 1 = N！（N-1）*（N-1）

2016-06-08 03:14:40 Brian

謝謝！我認爲你是對的。我不知道我爲什麼要考慮爲每一行提供可能的選擇。任何想法如何找到有向圖的答案？ –

對於有向圖，通過查看前面的行不會獲得有關任何行的信息，所以我會說它應該是N * N * N = N^N – Brian

@Brian E的作用是什麼（邊數）？例如，如果我們在有N個頂點的圖中有兩條邊，那麼我們可以有（nC2）*（n-1C2）個矩陣，因爲我們需要通過選擇任意兩個頂點來添加一條邊，並且必須添加第二條邊在另一對頂點之間，其中一個頂點不應來自步驟1中選擇的頂點。 –

回答