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, xlabel nz = 80 contains a line object which displays its values using only markers.

마지막으로, 다음은 spy 함수를 사용하여 전체 버키 볼 인접 행렬을 플로팅한 것입니다.

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

Figure contains an axes object. The axes object with title Bucky Ball Adjacency Matrix, xlabel nz = 180 contains a line object which displays its values using only markers.

참고 항목

|