algorithm - N个顶点和E条边的图有多少种不同的邻接矩阵？

Question

答案是N!我不明白这是怎么回事。

我的看法:

假设是无向图；

adj 中每一行的维度。一个顶点的矩阵是 N，与边数无关。因此，第一行可能的排列数 = N!。

第二行的总排列= (N-1)!因为第一行已经处理了一个单元格。同样，第三行=(N-2)!...对于第 N 行=1

总排列= N! + N-1!+...+1!

如果考虑无向图或有向图会产生不同的结果，我会感到困惑。如果我们认为图是有向的，答案会有什么变化？

Answer 1

我会试一试，但如果不清楚，请提问。对于它是 N!，我们假设一个无向图。

对于具有 N 个顶点的图，它将用 NxN 矩阵(二维数组)表示，每个值要么为 0(边不存在)，要么为 1(边存在)。在此，我们不考虑边上的其他权重。

然后，我们考虑所有可能的分配。如果第一行有 N 个不同的选择，则第二行必须有 N-1 个选择(因为我们已经知道边 1,2)，依此类推。

N * (N-1) * (N-2) * ... * 1 = N!