Загрузка данных

Загрузите набор данных barbellgraph.mat, который содержит разреженную матрицу смежности и координаты узла графика штанги.

load barbellgraph.mat

Построение графа

Постройте график с помощью пользовательских координат узла xy.

G = graph(A,'omitselfloops');
p = plot(G,'XData',xy(:,1),'YData',xy(:,2),'Marker','.');
axis equal

Вычисление матрицы Лапласа и вектора Fiedler

Вычислите Матрицу Лапласа графика. Затем вычислите два самых маленьких собственных значения величины и соответствующие собственные вектора с помощью eigs.

L = laplacian(G);
[V,D] = eigs(L,2,'smallestabs');

Вектор Fiedler является собственным вектором, соответствующим второму самому маленькому собственному значению графика. Самое маленькое собственное значение является нулем, указывая, что график имеет соединенный компонент того. В этом случае, второй столбец в V соответствует второму самому маленькому собственному значению D(2,2).

D

D = 2×2
10-3 ×

    0.0000         0
         0    0.2873

w = V(:,2);

Нахождение вектора Fiedler использование eigs масштабируемо к большим графикам, поскольку только подмножество собственных значений и собственных векторов вычисляется, но для меньших графиков одинаково выполнимо преобразовать Матрицу Лапласа в полное устройство хранения данных и использовать eig(full(L)).

Разделение графа

Разделите график в два подграфа с помощью вектора Fiedler w. Узел присвоен подграфу, если это имеет положительное значение в w. В противном случае узел присвоен подграфу B. Эта практика называется сокращением знака или нулевым пороговым сокращением. Сокращение знака минимизирует вес сокращения согласно верхним и нижним границам на весе любого нетривиального сокращения графика.

Разделите график с помощью сокращения знака. Подсветите подграф узлов с w>=0 в красном и узлах с w<0 в черном цвете.

highlight(p,find(w>=0),'NodeColor','r') % subgraph A
highlight(p,find(w<0),'NodeColor','k') % subgraph B

Для графика звонка панели этот раздел делит пополам график приятно в два равных набора узлов. Однако сокращение знака не всегда производит сбалансированное сокращение.

Всегда возможно разделить пополам график путем вычисления медианы w и использование его как пороговое значение. Этот раздел называется средним сокращением, и это гарантирует равное количество узлов в каждом подграфе.

Можно использовать медиану, сокращенную первым сдвигом значений в w медианой:

w_med = w - median(w);

Затем разделите график, входят в систему w_med. Для графика звонка панели, медианы w близко к нулю, таким образом, два сокращения производят подобные деления пополам.