유방향 그래프와 무방향 그래프

그래프란?

그래프는 관계를 나타내는 노드와 간선으로 구성된 모음입니다.

• 노드는 대응하는 객체를 나타내는 정점입니다.

• 간선은 객체 사이를 잇는 연결입니다.

• 그래프 간선은 경우에 따라 노드 사이를 잇는 각 연결의 강도(또는 일부 다른 특성(Attribute))를 나타내는 가중치를 갖습니다.

그래프에서 노드와 간선의 정확한 의미는 응용 사례에 따라 달라지므로 위와 같은 정의는 보편적인 것입니다. 예를 들어, 그래프를 사용하여 소셜 네트워크에서 친구 관계를 모델링할 수 있습니다. 그래프 노드는 사람이고, 간선은 친구 관계를 나타냅니다. 그래프는 기본적으로 실제 객체와 상황에 대응되므로, 사용자는 그래프를 사용하여 다양한 시스템을 모델링할 수 있습니다. 예를 들면 다음과 같습니다.

• 웹 페이지 링크 — 그래프 노드는 웹 페이지이고, 간선은 페이지 간 하이퍼링크를 나타냅니다.

• 공항 — 그래프 노드는 공항이고, 간선은 공항 간 항공편을 나타냅니다.

MATLAB^®에서 graph 함수와 digraph 함수는 무방향 그래프와 유방향 그래프를 나타내는 객체를 생성합니다.

• 무방향 그래프(Undirected Graph)는 방향이 없는 간선을 갖습니다. 간선은 양방향 관계를 나타내며, 각 간선은 양방향으로 진행할 수 있습니다. 다음 그림은 3개의 노드와 3개의 간선이 있는 간단한 무방향 그래프를 보여줍니다.

  

• 유방향 그래프(Directed Graph)는 방향이 있는 간선을 갖습니다. 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행할 수 있습니다. 다음 그림은 3개의 노드와 2개의 간선이 있는 간단한 유방향 그래프를 보여줍니다.

  

그래프 그림에 나와 있는 간선의 정확한 위치, 길이, 방향은 일반적으로 의미를 가지지 않습니다. 다시 말해서, 기본 구조를 변경하지 않는 경우에 한해, 노드를 재배열하거나 간선을 왜곡하여 동일한 그래프를 다양한 방법으로 시각화할 수 있습니다.

자가 루프와 다중 그래프

graph와 digraph를 사용하여 만든 그래프는 하나 이상의 자가 루프를 가질 수 있습니다. 자가 루프란 노드를 그 자신에게 연결하는 간선입니다. 또한 그래프는 소스 노드와 타깃 노드가 같은 여러 개의 간선을 가질 수 있으며, 이러한 그래프를 다중 그래프라고 합니다. 다중 그래프는 자가 루프를 포함할 수도 있고 포함하지 않을 수도 있습니다.

MATLAB의 그래프 알고리즘 함수에서는, 하나의 자가 루프를 갖는 노드가 포함된 그래프는 다중 그래프로 보지 않습니다. 반면, 그래프에 여러 개의 자가 루프를 갖는 노드가 있는 경우 이 그래프는 다중 그래프입니다.

예를 들어, 다음 그림에 자가 루프가 있는 무방향 다중 그래프가 있습니다. 노드 A는 세 개의 자가 루프를 갖는 반면, 노드 C는 하나의 자가 루프를 갖습니다. 이 그래프는 다음 세 가지 조건을 가지고 있는데, 이 중 하나라도 충족하면 다중 그래프가 됩니다.

• 노드 A는 3개의 자가 루프를 갖습니다.

• 노드 A와 B 사이에는 5개의 간선이 있습니다.

• 노드 A와 C 사이에는 2개의 간선이 있습니다.

어떤 그래프가 다중 그래프인지 파악하려면 ismultigraph 함수를 사용하십시오.

그래프 만들기

그래프를 만드는 기본적인 방법에는 인접 행렬이나 간선 목록을 사용하는 것이 있습니다.

인접 행렬

그래프에서 정보를 나타내는 한 가지 방법은 정사각 인접 행렬(Adjacency Matrix)을 사용하는 것입니다. 인접 행렬의 0이 아닌 항목은 두 노드 간 간선을 나타내고, 항목의 값은 간선의 가중치를 나타냅니다. 인접 행렬의 대각선 요소는 일반적으로 0이지만, 0이 아닌 대각선 요소는 자가 루프, 또는 간선이 자기 자신에 연결되는 노드를 나타냅니다.

• graph를 사용하여 무방향 그래프를 생성할 경우 인접 행렬은 대칭 행렬이어야 합니다. 실제로, 행렬은 반복을 피하기 위해 삼각 행렬인 경우가 많습니다. 인접 행렬의 상부 삼각 또는 하부 삼각만 사용하여 무방향 그래프를 생성하려면 graph(A,'upper') 또는 graph(A,'lower')를 사용하십시오.

• digraph를 사용하여 유방향 그래프를 생성할 경우 인접 행렬은 대칭 행렬일 필요가 없습니다.

• 대규모 그래프의 경우, 인접 행렬은 0을 많이 포함하며, 대개 희소 행렬입니다.

• 다중 그래프는 인접 행렬로 생성할 수 없습니다.

예를 들어, 다음과 같은 무방향 그래프를 살펴보겠습니다.

이 그래프는 아래와 같은 인접 행렬로 표현될 수 있습니다.

$$\left(\begin{array}{ccc}0& 1& 2\\ 1& 0& 3\\ 2& 3& 0\end{array}\right).$$

MATLAB에서 그래프를 생성하려면 다음을 입력하십시오.

A = [0 1 2; 1 0 3; 2 3 0];
node_names = {'A','B','C'};
G = graph(A,node_names)

G = 

  graph with properties:

    Edges: [3×2 table]
    Nodes: [3×1 table]

graph 함수나 digraph 함수를 사용하면 인접 행렬을 사용하여 그래프를 생성할 수 있습니다. 또는 adjacency 함수를 사용하여 기존 그래프의 가중 또는 비가중 희소 인접 행렬을 구할 수도 있습니다.

간선 목록

그래프에 정보를 나타내는 또 다른 방법은 모든 간선을 나열하는 것입니다.

예를 들어, 동일한 무방향 그래프를 살펴보겠습니다.

이제, 다음 간선 목록으로 그래프를 나타냅니다.

$$\begin{array}{l}\text{Edge Weight}\\ \begin{array}{cc}\begin{array}{c}(A,B)\\ (A,C)\end{array}& \begin{array}{c}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}& 1\end{array}& \end{array}& \end{array}\\ \begin{array}{cc}\begin{array}{cc}\begin{array}{cc}& 2\end{array}& \end{array}& \end{array}\end{array}\\ (B,C)& \begin{array}{cc}\begin{array}{cc}\begin{array}{cc}& 3\end{array}& \end{array}& \end{array}\end{array}\end{array}$$

간선 목록을 통해 그래프가 3개의 나열된 간선으로 연결된 3개의 고유한 노드 A, B, C를 가진다는 것을 쉽게 파악할 수 있습니다. 그래프에 연결되지 않은 노드가 있는 경우, 이러한 노드는 간선 목록에서 찾을 수 없으며 별도로 지정해야 합니다.

MATLAB에서 간선 목록은 열을 기준으로 소스 노드와 타깃 노드로 구분됩니다. 유방향 그래프의 경우 간선 방향(소스에서 타깃으로의 방향)이 중요하지만, 무방향 그래프의 경우에는 소스 노드와 타깃 노드를 서로 교환할 수 있습니다. 간선 목록을 사용하여 이 그래프를 생성하는 한 가지 방법은 소스 노드, 타깃 노드, 간선 가중치에 별도의 입력값을 사용하는 것입니다.

source_nodes = {'A','A','B'};
target_nodes = {'B','C','C'};
edge_weights = [1 2 3];
G = graph(source_nodes, target_nodes, edge_weights);

graph와 digraph는 모두 간선 목록으로부터 단순 그래프나 다중 그래프를 생성하는 것을 허용합니다. 그래프 G를 생성한 후에는 명령 G.Edges를 사용하여 간선과 간선 속성을 확인할 수 있습니다. G.Edges에 나와 있는 간선의 순서는 소스 노드(첫 번째 열)를 기준으로 정렬된 후 타깃 노드(두 번째 열)를 기준으로 정렬됩니다. 무방향 그래프의 경우, 더 작은 인덱스를 갖는 노드는 소스 노드로 나열되고 더 큰 인덱스를 갖는 노드는 타깃 노드로 나열됩니다.

graph와 digraph의 기본 구현은 희소 행렬에 종속되므로, 여러 인덱싱 비용이 동일하게 적용됩니다. 빈 그래프를 만들고 노드와 간선을 반복해서 추가하는 것보다 앞에서 언급한 방법 중 하나를 사용하여 3요소 쌍 (source,target,weight)에서 그래프를 한 번에 생성하는 것이 더 빠릅니다. 최상의 성능을 구현하려면 graph, digraph, addedge, addnode, rmedge 및 rmnode의 호출 횟수를 최소화하십시오.

그래프 노드 ID

기본적으로, graph나 digraph를 사용하여 만든 그래프에 포함된 모든 노드에는 번호가 지정됩니다. 따라서 언제든지 숫자형 노드 인덱스를 사용하여 노드를 참조할 수 있습니다.

또한, 그래프가 노드 이름을 가지는 경우(즉, G.Nodes가 변수 Name을 포함하는 경우) 해당 이름을 사용하여 그래프의 노드를 참조할 수 있습니다. 즉, 그래프에서 명명된 노드를 해당 노드 인덱스나 노드 이름으로 참조할 수 있습니다. 예를 들어, 노드 1을 'A'라고 할 수 있습니다.

노드 ID라는 용어는 노드 식별의 두 가지 측면을 모두 내포합니다. 노드 ID는 노드 인덱스와 노드 이름을 모두 나타냅니다.

편의를 위해, MATLAB은 사용자가 대부분의 그래프 함수를 호출할 때 사용하는 노드 ID의 유형을 기억합니다. 따라서, 노드 인덱스로 그래프의 노드를 참조하는 경우 대부분의 그래프 함수는 노드 인덱스로 노드를 참조하는 숫자형 답을 반환합니다.

A = [0 1 1 0; 1 0 1 0; 1 1 0 1; 0 0 1 0];
G = graph(A,{'a','b','c','d'});
p = shortestpath(G,1,4)

p =

     1     3     4

그러나, 노드 이름으로 노드를 참조하는 경우 대부분의 그래프 함수는 노드 이름(문자형 벡터로 구성된 셀형 배열 또는 string형 배열에 포함됨)으로 노드를 참조하는 답을 반환합니다.

p1 = shortestpath(G,'a','d')

p1 =

  1×3 cell array

    {'a'}    {'c'}    {'d'}

findnode를 사용하여 지정된 노드 이름에 대한 숫자형 노드 ID를 구할 수 있습니다. 반대로, 지정된 숫자형 노드 ID에 대해서는 G.Nodes.Name의 요소를 참조하여 대응되는 노드 이름을 확인할 수 있습니다.

기존 그래프를 수정하거나 쿼리하기

graph 객체나 digraph 객체를 생성한 후에는 다양한 함수를 사용하여 그래프 구조를 수정하거나 그래프에 포함된 노드 개수나 간선 개수를 확인할 수 있습니다. 다음 표에는 graph 객체와 digraph 객체를 수정하거나 쿼리하는 데 사용할 수 있는 일부 함수가 나와 있습니다.

addedge	그래프에 하나 이상의 간선을 추가합니다.
rmedge	그래프에서 하나 이상의 간선을 제거합니다.
addnode	그래프에 하나 이상의 노드를 추가합니다.
rmnode	그래프에서 하나 이상의 노드를 제거합니다.
findnode	그래프에서 특정 노드를 찾습니다.
findedge	그래프에서 특정 간선을 찾습니다.
numnodes	그래프에 포함된 노드 개수를 구합니다.
numedges	그래프에 포함된 간선 개수를 구합니다.
edgecount	지정된 노드 사이의 간선 개수를 구합니다.
flipedge	유방향 그래프 간선의 방향을 반대로 바꿉니다.
reordernodes	그래프에 포함된 노드의 순서를 바꿉니다.
subgraph	부분 그래프(Subgraph)를 추출합니다.

일반적인 몇 가지 그래프 수정 예제를 보려면 기존 그래프의 노드와 간선 수정하기 항목을 참조하십시오.

참고 항목

graph | digraph

관련 항목

• 기존 그래프의 노드와 간선 수정하기
• 그래프 노드 이름, 간선 가중치, 기타 특성(Attribute) 추가하기
• 그래프 플로팅과 사용자 지정