Матричный формализм NxN матрица смежности

Question

Пусть A - матрица смежности NxN неориентированной невзвешенной сети без самоконтролей.Пусть 1 будет вектором столбца из N элементов, все равны 1. Другими словами 1 = (1, 1, ..., 1) T, где верхний индекс T указывает на операцию транспонирования.Используйте матричный формализм (мультипликативные константы, умножение строка за столбцом, матричные операции, такие как транспонирование и трассировка и т. Д., Но избегайте символа суммы Σ), чтобы записать выражения для:

a) Вектор k, элементами которого являются градусыki всех узлов i = 1, 2, ..., N.

b) Общее количество ребер L в сети.

d) Количество имеющихся треугольников Tв сети, где треугольник означает три узла, каждый из которых связан ссылками с двумя другими (Совет: вы можете использовать трассировку матрицы).

Answer 1

а) умножьте матрицу смежности на 1 (вектор, который вы упомянули); б) используйте (1, 1,…, 1) * (вектор из а) T, который дает вам сумму всех элементов в матрице смежности,это число всех ребер.в) существует теорема.Пусть A - матрица смежности, тогда A ^ k [i] [j] дает вам количество путей длины k от узла i до узла j.Если вы затем вычислите A ^ 3 и посмотрите на диагональные элементы (i), они дадут вам количество путей от узла i к себе длиной 3, которые являются так называемыми треугольниками.Если вы затем учитываете все перестановки, ответом будет сумма (след (A ^ 3)) / 6.