Как найти узлы треугольника из матрицы смежности в Octave

avatar
Fay007
14 июня 2020 в 15:56
262
2
1

Я знаю, как найти количество треугольников в матрице смежности.

tri = trace(A^3) / 6

Но мне нужно найти узлы, чтобы наконец найти значение ребер из матрицы смежности, так как это граф знаков. Есть ли уже существующая функция, которая это делает?

Источник

Ответы (2)

avatar
beaker
14 июня 2020 в 20:29
3

При взятии мощности матрицы смежности теряется информация о промежуточных узлах. Вместо 2-мерной матрицы нам нужны 3 измерения.

Данный график:

enter image description here

и его матрица смежности:

A =

  0  0  0  0  1  1  0  1  0  0
  0  0  0  1  0  1  0  0  0  0
  0  0  0  1  0  0  0  1  0  1
  0  1  1  0  1  0  1  0  0  0
  1  0  0  1  0  0  1  0  0  0
  1  1  0  0  0  0  0  1  1  0
  0  0  0  1  1  0  0  0  1  0
  1  0  1  0  0  1  0  0  0  0
  0  0  0  0  0  1  1  0  0  0
  0  0  1  0  0  0  0  0  0  0

Вычислить трехмерную матрицу T, такую, что T(i,j,k) == 1 тогда и только тогда, когда в графе есть путь i=>j=>k=>i.

T = and(A, permute(A, [3 1 2]))

Это эквивалент возведения в квадрат матрицы смежности, но с сохранением информации о пути. and используется здесь вместо умножения в случае, если A является взвешенной матрицей смежности. Если вы суммируете по 2-му измерению, вы получите A^2:

>> isequal(squeeze(sum(T,2)), A^2)

ans = 1

Теперь, когда у нас есть пути длины 2, нам просто нужно отфильтровать, чтобы оставить только пути, которые возвращаются к исходным точкам.

T = and(T, permute(A.', [1 3 2]));   % Transpose A in case graph is directed

Теперь, если T(i,j,k) == 1, то существует треугольник, начинающийся с узла i, через узлы j и k и возвращающийся к узлу i. Если вы хотите найти все такие пути:

[M,N,P] = ind2sub(size(T), find(T));
P = [M,N,P];

P будет списком всех треугольных путей:

P =

   8   6   1
   6   8   1
   7   5   4
   5   7   4
   7   4   5
   4   7   5
   8   1   6
   1   8   6
   5   4   7
   4   5   7
   6   1   8
   1   6   8

В этом случае мы получаем 12 путей. Все пути в неориентированном графе имеют 6 дубликатов: по одному, начинающемуся в каждой точке треугольника, умноженному на 2 направления. Это дает те же результаты, что и trace:

.
>> trace(A^3)
ans =  12

Если вы хотите удалить дубликаты, самый простой способ для треугольников — просто отсортировать порядок вершин, а затем взять уникальные строки списка. Это работает для треугольников только потому, что присутствуют все перестановки узлов в цикле. Для более длинных циклов это не сработает.

P = unique(sort(P, 2), 'rows');

P = 
   1   6   8
   4   5   7
Fay007
15 июня 2020 в 18:19
0

Есть ли способ избежать дубликатов?

beaker
15 июня 2020 в 18:30
1

Что, кстати, является тем же подходом, который использует rahnema1.

avatar
rahnema1
15 июня 2020 в 06:16
2

Вот решение с использованием умножения матриц:

  C = (A * A.') & A;
  [x, y] = find(tril(C));
  n = numel(x);
  D = sparse([x; y], [1:n 1:n].', 1, size(A,1), n);
  [X, ~, V] = find(C * D);
  tri = [x y X(V == 2)]
  tri = unique(sort(tri, 2), 'rows');

Сначала нам нужно узнать, что такое узлы треугольника. Два узла являются узлами треугольника, если они имеют общего соседа и оба являются соседями друг друга. Мы берем определение для вычисления матрицы смежности C, которая содержит только узлы треугольника, а все остальные узлы удаляются.

Выражение A * A.' выбирает узлы, имеющие общих соседей, а оператор & A говорит, что те узлы, которые имеют общих соседей, должны быть соседями друг друга.

Теперь мы можем использовать [x, y] = find(tril(C)); для извлечения первой и второй точек каждого треугольника как x и y соответственно.

Для третьего узла нам нужно найти узел, у которого есть x и y в качестве его соседей. Как и раньше, мы можем использовать трюк с умножением булевых матриц для ускорения вычислений. Наконец, результат tri содержит дубликаты, которые следует удалить с помощью unique и sort.

.