Napisałem funkcję, która, biorąc pod uwagę n, generuje losowe macierze przyległości nxn. Zastanawiałem się, czy istnieje sposób policzenia liczby trójkątów na wykresie reprezentowanym przez macierz.Biorąc pod uwagę macierz sąsiedztwa nxn, jak można obliczyć liczbę trójkątów na wykresie (Matlab)?
The (i, J) element n -tym mocy matrycy przylegania A zlicza liczbę ścieżek długości n wyjściowego w i a kończąc na j.
Trójkąt to ścieżka o długości 3, która rozpoczyna się i kończy w tym samym węźle. Dlatego też, element przekątnej trzeciej potęgi A zlicza liczbę trójkątów, które zawierają i jako jeden z węzłów.
Każdy odrębny trójkąt zostanie policzony dwukrotnie dla każdego z trzech węzłów na wykresie (jeden raz w każdym kierunku, zgodnie z ruchem wskazówek zegara i przeciwnie do ruchu wskazówek zegara).
W związku z tym liczba trójkątów odrębnych wynosi trace(A^3)/6.