Перетасовка матрицы смежности неориентированного случайного графа на основе связности

У меня есть матрица смежности nxn A неориентированного случайного графа, поэтому Aij может быть либо 0, либо 1. Если Aij равно 1, это означает, что между узлами ith и jth есть ребро. Если он равен 0, это означает, что между ними нет границы.

Я хочу перетасовать матрицу на основе степени вершин. Все вершины, степень которых меньше, чем равная k, я хочу поместить в конец. Допустим, таких вершин m, поэтому последние m строки и столбцы моей новой матрицы смежности будут представлять эти вершины.

Я хочу реализовать это в MATLAB. Я понятия не имею, как решить это эффективно. Только кажется, что я знаю, как находить такие вершины.

a = 1:n;
ver = a(sum(A) < k+1 );

Любая помощь приветствуется.


matlab graph adjacency-matrix
person Rajat    schedule 03.12.2015    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Поскольку ваш граф неориентирован, ваша матрица смежности A симметрична. Как вы уже заметили, вы можете определить степень вершин, просто суммируя строки (или столбцы) A:

deg = sum(A, 2);

Теперь вы можете sort вычислять вершины по степени

[sd si] = sort(deg, 'decrease'); %// sort in a decreasing order

Вы можете использовать отсортированные индексы (si), чтобы переупорядочить A:

A = A(si,si);

Обратите внимание, что вы ДОЛЖНЫ применить одну и ту же перестановку как к строкам, так и к столбцам A, иначе...

Теперь, когда ваш граф упорядочен по степени вершин, один раз с меньшей степенью, естественно, будет в конце A.

person Shai    schedule 03.12.2015
comment
Хорошо замечено применение одной и той же перестановки к столбцам! - person Luis Mendo; 03.12.2015
comment
да. Хороший. Я полностью упустил из виду возможность сортировки на основе подключения. Еще раз спасибо. - person Rajat; 03.12.2015