Загрузить данные

Загрузить набор данных 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 близок к нулю, поэтому два разреза производят одинаковые биссектрисы.