Main Content

그래프와 행렬

이 예제에서는 희소 행렬의 응용 예를 보여주고 그래프와 행렬 사이의 관계에 대해 설명합니다.

그래프는 노드 사이에 연결, 즉 간선이 지정된 노드의 집합입니다. 그래프는 여러 형태와 크기가 될 수 있습니다. 한 예로 버크민스터 풀러(Buckminster Fuller)의 측지선 돔(Geodesic Dome)의 연결 그래프를 들 수 있으며, 이는 축구공이나 C60 분자의 형태이기도 합니다.

MATLAB®에서는 bucky 함수를 사용하여 측지선 돔의 그래프를 생성할 수 있습니다.

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

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

또한 노드의 좌표를 지정하여 그래프의 표시를 변경할 수도 있습니다.

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

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

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

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

이 반구의 인접 행렬을 시각화하기 위해 spy 함수를 사용하여 인접 행렬에서 0이 아닌 요소의 윤곽을 플로팅해 보겠습니다.

참고로, 이 행렬은 대칭 행렬입니다. 노드 i가 노드 j에 연결되어 있으면 노드 j가 노드 i에 연결되어 있기 때문입니다.

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

Figure contains an axes object. The axes object 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 object. The axes object with title Bucky Ball Adjacency Matrix contains an object of type line.

참고 항목

|