Этот пример показывает применение разреженных матриц и объясняет связь между графиками и матрицами.
График является набором узлов с заданными соединениями, или ребрами, между ними. Графики имеют много форм и размеров. Одним из примеров является графиков связности геодезического купола Бакминстера Фуллера, который также имеет форму футбольного мяча или молекулы углерода-60.
В MATLAB ® можно использовать bucky функция для генерации графика геодезического купола.
[B,V] = bucky;
G = graph(B);
p = plot(G);
axis equal
Можно также задать координаты для узлов, чтобы изменить отображение графика.
p.XData = V(:,1); p.YData = V(:,2);
The bucky функция может использоваться, чтобы создать график, потому что она возвращает матрицу смежности. Матрица смежности является одним из способов представления узлов и ребер в графике.
Чтобы создать матрицу смежности графика, узлы нумеруются 1 к N. Затем каждый элемент (i, j) матрицы N на N устанавливается равным 1, если узел i соединён с узлом j, и 0 в противном случае. Таким образом, для неориентированных графов матрица смежности симметрична, но это не должно быть в случае ориентированных графов.
Для примера вот простой график и связанная с ней матрица смежности.
% Define a matrix A. A = [0 1 1 0 ; 1 0 0 1 ; 1 0 0 1 ; 0 1 1 0]; % Draw a picture showing the connected nodes. cla subplot(1,2,1); gplot(A,[0 1;1 1;0 0;1 0],'.-'); text([-0.2, 1.2 -0.2, 1.2],[1.2, 1.2, -.2, -.2],('1234')', ... 'HorizontalAlignment','center') axis([-1 2 -1 2],'off') % Draw a picture showing the adjacency matrix. subplot(1,2,2); xtemp = repmat(1:4,1,4); ytemp = reshape(repmat(1:4,4,1),16,1)'; text(xtemp-.5,ytemp-.5,char('0'+A(:)),'HorizontalAlignment','center'); line([.25 0 0 .25 NaN 3.75 4 4 3.75],[0 0 4 4 NaN 0 0 4 4]) axis off tight
Разреженные матрицы особенно полезны для представления очень больших графиков. Это происходит потому, что каждый узел обычно соединяется только с несколькими другими узлами. В результате плотность ненулевых записей в матрице смежности часто относительно мала для больших графиков. Матрица смежности мяч является хорошим примером, поскольку это симметричная разреженная матрица 60 на 60 с только 180 ненулевыми элементами. Плотность этой матрицы всего 5%.
Поскольку матрица смежности задает граф, можно построить график фрагмента bucky ball с помощью подмножества записей в матрице смежности.
Используйте adjacency функция для создания новой матрицы смежности для графика. Отобразите узлы в одном полусфере bucky ball путем индексации в матрицу смежности, чтобы создать новый меньший график.
figure A = adjacency(G); H = graph(A(1:30,1:30)); h = plot(H);
Чтобы визуализировать матрицу смежности этого полушария, используйте spy функция для построения графика силуэта ненулевых элементов в матрице смежности.
Обратите внимание, что матрица симметрична, поскольку если узел i соединен с узлом j, то узел j соединяется с узлом i.
spy(A(1:30,1:30))
title('Top Left Corner of Bucky Ball Adjacency Matrix')
Наконец, вот spy график всей матрицы смежности мяч.
spy(A)
title('Bucky Ball Adjacency Matrix')