Ich schrieb eine Funktion, die, gegeben n, zufällige nxn Adjazenzmatrizen generiert. Ich habe mich gefragt, ob es eine Möglichkeit gibt, die Zahl als Dreiecke im Graphen zu bezeichnen, der durch die Matrix dargestellt wird.Mit einer nxn Adjazenzmatrix, wie kann man die Anzahl der Dreiecke im Graphen berechnen (Matlab)?
Die (i, j) Element in der n ‚te Potenz eines Adjazenzmatrix A zählt die Anzahl der Wege der Länge n bei beginnend i und endend bei j.
Ein Dreieck ist ein Pfad der Länge 3, der am selben Knoten beginnt und endet. Daher zählt die i 'Diagonale Element der 3. Potenz von A die Anzahl der Dreiecke, die i als einen der Knoten enthalten.
Jedes einzelne Dreieck wird zweimal für jeden der drei Knoten im Diagramm gezählt (einmal in jede Richtung, im Uhrzeigersinn und gegen den Uhrzeigersinn).
Daher ist die Anzahl der verschiedenen Dreiecke trace(A^3)/6.