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

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

load barbellgraph.mat

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

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

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

Вычислите Матрицу Лапласа и вектор Фидлера

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

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

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

D

D = 2×2
10-3 ×

    0.0000         0
         0    0.2873

w = V(:,2);

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

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

Разбейте график на две подграфики с помощью вектора Фидлера w. Узел назначается подграфу A, если он имеет положительное значение в 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 близок к нулю, поэтому эти два разреза производят одинаковые бисекции.