Графы и матрицы

Этот пример показывает приложение разреженных матриц и объясняет отношение между графиками и матрицами.

График является набором узлов с заданными связями или ребрами, между ними. Графики появляются во многие формы и размеры. Одним примером является график возможности соединения Бакминстера Фуллера геодезический купол, который является также в форме футбольного мяча или углерода 60 молекулами.

В MATLAB® можно использовать bucky функция, чтобы сгенерировать график геодезического купола.

[B,V] = bucky;
G = graph(B);
p = plot(G);
axis equal

Также можно задать координаты для узлов, чтобы изменить отображение графика.

p.XData = V(:,1);
p.YData = V(:,2);

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%.

Поскольку матрица смежности задает график, можно построить фрагмент маркерного шара при помощи подмножества записей в матрице смежности.

Используйте adjacency функция, чтобы создать новую матрицу смежности для графика. Отобразите узлы в одном полушарии маркерного шара путем индексации в матрицу смежности, чтобы создать новый, меньший график.

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')

Смотрите также

|

Для просмотра документации необходимо авторизоваться на сайте