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

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

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

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

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

Figure contains an axes. The axes contains an object of type graphplot.

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

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

Figure contains an axes. The axes contains an object of type graphplot.

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

Figure contains an axes. The axes contains an object of type graphplot.

Чтобы визуализировать матрицу смежности этого полушария, используйте spy функционируйте, чтобы построить контур ненулевых элементов в матрице смежности.

Обратите внимание на то, что матрица симметрична, с тех пор, если узел i соединяюсь с узлом j, затем узел j соединяется с узлом i.

spy(A(1:30,1:30))
title('Top Left Corner of Bucky Ball Adjacency Matrix')

Figure contains an axes. The axes with title Top Left Corner of Bucky Ball Adjacency Matrix contains an object of type line.

Наконец, вот spy график целой маркерной матрицы смежности мяча.

spy(A)
title('Bucky Ball Adjacency Matrix')

Figure contains an axes. The axes with title Bucky Ball Adjacency Matrix contains an object of type line.

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

|

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