Wie viele verschiedene Adjazenzmatrix hat ein Graph mit N Ecken und E Kanten?

Question

Die Antwort ist N! und ich verstehe nicht wie es ist.

Meine Ansicht:

Unter der Annahme, es ein ungerichteter Graph ist;

Die Dimension jeder Zeile in einem adj. Die Matrix eines Eckpunkts ist N unabhängig von der Anzahl der Kanten. Daher ist die Anzahl der möglichen Permutationen für die erste Zeile = N !.

Gesamtpermutation für die zweite Zeile = (N-1)! seit einer Zelle ist schon in der ersten Reihe aufgepasst worden. Ähnlich, dritte Zeile = (N-2)! . . . Für N-te Reihe = 1

Gesamtpermutation = N! + N-1! + ... + 1!

Ich bin verwirrt, wenn ein ungerichtetes oder gerichtetes Diagramm zu einem anderen Ergebnis führt oder nicht. Wie wird sich die Antwort ändern, wenn wir den Graph als gerichtet betrachten?

Answer 1

Ich werde eine Chance darauf nehmen, aber bitte stellen Sie Fragen, wenn es unklar ist. Damit es N ist, nehmen wir eine ungerichtete Graphik an.

Für einen Graph mit N Vertices würde es mit einer NxN-Matrix (2D-Array) dargestellt werden, wobei jeder Wert entweder 0 (Kante existiert nicht) oder 1 (Kante existiert) ist. Dabei berücksichtigen wir keine anderen Gewichte an Kanten.

Dann betrachten wir alle möglichen Zuordnungen. Wenn es in der ersten Reihe N verschiedene Auswahlen gibt, müssen in der zweiten Reihe N-1 Auswahlen sein (da wir bereits über die Kante 1,2 wissen) und so weiter.

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