그래프와 행렬
이 예제에서는 희소 행렬의 응용 예를 보여주고 그래프와 행렬 사이의 관계에 대해 설명합니다.
그래프는 노드 사이에 연결, 즉 간선이 지정된 노드의 집합입니다. 그래프는 여러 형태와 크기가 될 수 있습니다. 한 예로 버크민스터 풀러(Buckminster Fuller)의 측지선 돔(Geodesic Dome)의 연결 그래프를 들 수 있으며, 이는 축구공이나 C60 분자의 형태이기도 합니다.
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 행렬의 각 요소 (i,j)가 1로 설정되고, 그렇지 않으면 0으로 설정됩니다. 따라서 무방향 그래프의 경우 인접 행렬은 대칭 행렬이지만, 유방향 그래프의 경우는 반드시 그렇지는 않습니다.
예를 들어, 아래에서는 단순 그래프(simple graph) 및 이와 관련된 인접 행렬을 보여줍니다.
% 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
희소 행렬은 매우 큰 그래프를 나타내는 데 특히 유용합니다. 각 노드가 대개 몇 개의 다른 노드에만 연결되어 있기 때문입니다. 따라서, 큰 그래프의 경우 인접 행렬에서 0이 아닌 요소의 밀도가 비교적 작은 경우가 종종 있습니다. 한 좋은 예로 버키 볼(Bucky Ball)의 인접 행렬을 들 수 있습니다. 이 행렬은 60×60 대칭 희소 행렬로, 0이 아닌 요소가 180개밖에 되지 않습니다. 이 행렬의 밀도는 5%에 불과합니다.
인접 행렬은 그래프를 정의하므로, 인접 행렬의 요소로 구성된 부분 집합을 사용하여 버키 볼의 일부를 플로팅할 수 있습니다.
adjacency
함수를 사용하여 그래프의 새 인접 행렬을 만들어 보겠습니다. 더 작은 새 그래프를 만들기 위해 인접 행렬을 인덱싱하여 버키 볼의 한쪽 반구에 있는 노드를 표시합니다.
figure A = adjacency(G); H = graph(A(1:30,1:30)); h = plot(H);
이 반구의 인접 행렬을 시각화하기 위해 spy
함수를 사용하여 인접 행렬에서 0이 아닌 요소의 윤곽을 플로팅해 보겠습니다.
참고로, 이 행렬은 대칭 행렬입니다. 노드 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')