Main Content

graph

무방향 간선이 있는 그래프

설명

graph 객체는 방향 없는 간선으로 노드를 연결하는 무방향 그래프를 나타냅니다. graph 객체를 생성한 후에는 객체 함수를 통해 객체에 대해 쿼리를 수행하여 그래프에 대한 자세한 내용을 확인할 수 있습니다. 예를 들어, 노드나 간선을 추가 또는 제거하거나, 두 노드 사이의 최단 경로를 확인하거나, 특정 노드나 간선을 찾을 수 있습니다.

G = graph([1 1], [2 3]);
e = G.Edges
G = addedge(G,2,3)
G = addnode(G,4)
plot(G)

생성

설명

예제

G = graph는 노드나 간선이 없는 비어 있는 무방향 graph 객체 G를 생성합니다.

예제

G = graph(A)는 정사각 대칭 인접 행렬 A를 사용하여 그래프를 생성합니다.

  • 논리형 인접 행렬에 대해 그래프는 간선 가중치를 갖지 않습니다.

  • 비논리형 인접 행렬에 대해 그래프는 간선 가중치를 갖습니다. A의 0이 아닌 각 요소의 위치는 그래프의 간선을 지정하며, 간선의 가중치는 해당 요소의 값과 같습니다. 예를 들어, A(2,1) = 10이면 G의 노드 2와 노드 1 사이에 가중치가 10인 간선이 포함됩니다.

예제

G = graph(A,nodenames)는 추가로 노드 이름을 지정합니다. nodenames의 요소 개수는 size(A,1)과 같아야 합니다.

G = graph(A,NodeTable)은 테이블 NodeTable을 사용하여 노드 이름(그리고, 가능한 기타 노드 특성)을 지정합니다. 이 테이블은 A와 행 개수가 동일해야 합니다. 테이블 변수 Name을 사용하여 노드 이름을 지정합니다.

예제

G = graph(A,___,type)은 그래프를 생성하는 데 사용할 인접 행렬의 삼각 행렬을 지정합니다. A는 반드시 지정해야 하며, nodenames 또는 NodeTable을 선택적으로 지정할 수 있습니다. A의 상부 삼각이나 하부 삼각만 사용하여 그래프를 생성하려는 경우 type'upper' 또는 'lower'일 수 있습니다.

예제

G = graph(A,___,'omitselfloops')A의 대각선 요소를 무시하고 자가 루프가 없는 그래프를 반환합니다. 위에 열거된 구문에 나와 있는 입력 인수를 원하는 대로 조합하여 사용할 수 있습니다.

예제

G = graph(s,t)는 그래프 간선 (s,t)를 노드 쌍으로 지정합니다. st는 노드 인덱스 또는 노드 이름을 지정할 수 있습니다. graphG의 간선을 먼저 소스 노드를 기준으로 정렬한 다음 타깃 노드를 기준으로 정렬합니다. st와 순서가 같은 간선 속성이 있는 경우 결과로 생성되는 그래프에서 간선이 동일한 방식으로 정렬되도록 G = graph(s,t,EdgeTable) 구문을 사용하여 간선 속성을 전달하십시오.

예제

또한 G = graph(s,t,weights)는 배열 weights로 간선 가중치도 지정합니다.

예제

G = graph(s,t,weights,nodenames)는 문자형 벡터로 구성된 셀형 배열 또는 string형 배열 nodenames를 사용하여 노드 이름을 지정합니다. st에는 nodenames에 없는 노드 이름을 사용할 수 없습니다.

G = graph(s,t,weights,NodeTable)은 테이블 NodeTable을 사용하여 노드 이름(그리고, 가능한 기타 노드 특성)을 지정합니다. Name 테이블 변수를 사용하여 노드 이름을 지정합니다. st에는 NodeTable에 없는 노드 이름을 사용할 수 없습니다.

예제

G = graph(s,t,weights,num)은 숫자형 스칼라 num으로 그래프의 노드 개수를 지정합니다.

G = graph(s,t,___,'omitselfloops')는 그래프에 자가 루프를 추가하지 않습니다. 즉, s(k) == t(k)를 충족하는 k는 무시됩니다. 위에 열거된 구문에 나와 있는 입력 인수를 원하는 대로 조합하여 사용할 수 있습니다.

G = graph(s,t,EdgeTable,___)weights를 지정하는 대신 테이블을 사용하여 간선 특성을 지정합니다. EdgeTable 입력값은 s에 있는 요소와 t에 있는 요소의 각 대응 쌍에 대한 행이 포함된 테이블이어야 합니다. 테이블 변수 Weight를 사용하여 간선 가중치를 지정합니다.

예제

G = graph(EdgeTable)은 테이블 EdgeTable을 사용하여 그래프를 정의합니다. 이 구문에서 EdgeTable의 첫 번째 변수 이름은 반드시 EndNodes여야 하며, 이 변수는 그래프 간선 목록을 정의하는 2열 배열이어야 합니다.

예제

G = graph(EdgeTable,NodeTable)은 테이블 NodeTable을 사용하여 그래프 노드의 이름(그리고, 가능한 기타 특성)을 추가로 지정합니다.

G = graph(EdgeTable,___,'omitselfloops')는 그래프에 자가 루프를 추가하지 않습니다. 즉, EdgeTable.EndNodes(k,1) == EdgeTable.EndNodes(k,2)를 충족하는 k는 무시됩니다. EdgeTable은 반드시 지정해야 하며, NodeTable을 선택적으로 지정할 수 있습니다.

입력 인수

모두 확장

인접 행렬로, 비희소(Full) 형식 또는 희소 형식의 숫자형 행렬로 지정됩니다. A의 요소는 그래프의 노드 사이의 연결 네트워크(간선)를 지정합니다. A에서 0이 아닌 각 요소의 위치는 두 노드 사이의 간선을 지정합니다. 그 요소의 값은 간선 가중치를 제공합니다. 논리형 인접 행렬의 경우 비가중 그래프(Unweighted Graph)가 생성됩니다.

A의 주대각선상에 있는 0이 아닌 요소는 자가 루프 즉, 간선으로 자기 자신에 연결되는 노드를 지정합니다. 대각선상의 요소를 무시하려면 'omitselfloops' 입력 옵션을 사용하십시오.

type 입력값을 지정하지 않는 한 A는 대칭 행렬이어야 합니다. 행렬의 대칭성을 확인하려면 issymmetric을 사용하십시오. 삼각 인접 행렬의 경우 type을 지정하여 상부 삼각 또는 하부 삼각만 사용하십시오.

예: A = [0 1 5; 1 0 0; 5 0 0]은 3개의 노드와 2개의 간선이 있는 그래프를 설명합니다. 노드 1과 노드 2 사이의 간선은 가중치가 1이고, 노드 1과 노드 3 사이의 간선은 가중치가 5입니다.

데이터형: single | double | logical

노드 이름으로, 문자형 벡터로 구성된 셀형 배열 또는 string형 배열로 지정됩니다. nodenames는 길이가 numnodes(G)와 같아야 하며, 그래프의 각 노드에 대한 비어 있지 않은 고유한 이름을 포함해야 합니다.

예: G = graph(A,{'n1','n2','n3'})은 3×3 인접 행렬 A에 대해 세 개의 노드 이름을 지정합니다.

데이터형: cell | string

인접 행렬 유형으로, 'upper' 또는 'lower'로 지정됩니다.

예: G = graph(A,'upper')A의 상부 삼각만 사용하여 그래프 G를 생성합니다.

노드 쌍으로, 노드 인덱스 또는 노드 이름으로 지정됩니다. graphst의 대응하는 노드 사이에 간선을 생성합니다. s와 t는 모두 숫자형이거나, 모두 문자형 벡터, 문자형 벡터로 구성된 셀형 배열, string형 배열 또는 categorical형 배열이어야 합니다. 어떤 경우이든 st의 요소 개수는 같아야 합니다.

  • st가 숫자형이면 그래프 노드의 인덱스에 대응됩니다. 숫자형 노드 인덱스는 1보다 크거나 같은 양의 정수여야 합니다.

  • st가 문자형 벡터, 문자형 벡터로 구성된 셀형 배열 또는 string형 배열이면 노드의 이름을 지정합니다. 그래프의 Nodes 속성은 노드 이름 G.Nodes.Name을 가진 Name 변수를 포함하는 테이블입니다.

  • st가 categorical형 배열인 경우 st의 범주는 그래프의 노드 이름으로 사용됩니다. 여기에는 s 또는 t의 요소가 아닌 범주도 포함될 수 있습니다.

  • st가 동일한 두 노드 사이의 다중 간선을 지정하는 경우, 결과는 다중 그래프가 됩니다.

다음 표에서는 숫자형 노드 인덱스 또는 노드 이름을 사용하여 하나 이상의 노드를 참조하는 몇 가지 방법을 보여줍니다.

형식단일 노드여러 노드
노드 인덱스

스칼라

예: 1

벡터

예: [1 2 3]

노드 이름

문자형 벡터

예: 'A'

문자형 벡터로 구성된 셀형 배열

예: {'A' 'B' 'C'}

string형 스칼라

예: "A"

string형 배열

예: ["A" "B" "C"]

categorical형 배열

예: categorical("A")

categorical형 배열

예: categorical(["A" "B" "C"])

예: G = graph([1 2 3],[2 4 5])는 5개의 노드와 3개의 간선이 있는 그래프를 생성합니다.

예: G = graph({'Boston' 'New York' 'Washington D.C.'},{'New York' 'New Jersey' 'Pittsburgh'})는 명명된 노드 5개와 간선 3개가 있는 그래프를 생성합니다.

간선 가중치로, 스칼라, 벡터, 행렬 또는 다차원 배열로 지정됩니다. weights는 스칼라이거나 요소 개수가 st와 동일한 배열이어야 합니다.

graph는 간선 가중치를 G.Edges 속성 테이블에 Weight 변수로 저장합니다. 그래프를 생성한 후 가중치를 추가하거나 변경하려면 테이블 변수를 직접 수정하면 됩니다(예: G.Edges.Weight = [25 50 75]').

weights를 빈 배열 []로 지정하면 가중치는 무시됩니다.

예: G = graph([1 2],[2 3],[100 200])은 3개의 노드와 2개의 간선이 있는 그래프를 생성합니다. 간선은 100200의 가중치를 가집니다.

데이터형: single | double

그래프 노드 개수로, 양의 정수 스칼라로 지정됩니다. numst의 가장 큰 요소보다 크거나 같아야 합니다.

예: G = graph([1 2],[2 3],[],5)는 연결된 노드 3개와 고립된(Isolated) 노드 2개가 있는 그래프를 생성합니다.

간선 정보 테이블입니다. st를 지정하지 않으면 EdgeTable의 첫 번째 변수는 그래프 간선을 정의하는 2열 행렬, 문자형 벡터로 구성된 셀형 배열 또는 string형 배열이고 EndNodes라는 이름을 가져야 합니다. 간선 가중치의 경우, 이 테이블 변수 이름이 일부 그래프 함수에서 사용되므로 변수 Weight를 사용하십시오. 변수 Weight가 있는 경우 해당 값은 숫자형 열 벡터여야 합니다. 테이블을 생성하는 방법에 대한 자세한 내용은 table을 참조하십시오.

그래프를 생성한 후 G.Edges를 사용하여 간선 정보 테이블을 쿼리합니다.

예: EdgeTable = table([1 2; 2 3; 3 5; 4 5],'VariableNames',{'EndNodes'})

데이터형: table

노드 정보 테이블입니다. NodeTable은 그래프 노드의 특성을 설명할 변수를 원하는 수만큼 포함할 수 있습니다. 노드 이름의 경우, 이 변수 이름이 일부 그래프 함수에서 사용되므로 변수 Name을 사용하십시오. 변수 Name이 있는 경우 그 값은 각 행의 고유 이름을 지정하는 문자형 벡터로 구성된 셀형 배열 또는 string형 배열이어야 합니다. 테이블을 생성하는 방법에 대한 자세한 내용은 table을 참조하십시오.

그래프를 생성한 후 G.Nodes를 사용하여 노드 정보 테이블을 쿼리합니다.

예: NodeTable = table({'a'; 'b'; 'c'; 'd'},'VariableNames',{'Name'})

데이터형: table

속성

모두 확장

그래프의 간선으로, 테이블로 반환됩니다. 기본적으로 M×1 테이블이며, 여기서 M은 그래프의 간선 개수입니다. G.Edges.EndNodes의 간선 목록은 먼저 소스 노드를 기준으로 정렬된 다음 타깃 노드를 기준으로 정렬됩니다.

  • 그래프에 새 간선 속성을 추가하려면 Edges 테이블에 새 변수를 생성하십시오.

  • 그래프에 간선을 추가하려면 addedge 객체 함수를 사용하고 제거하려면 rmedge 객체 함수를 사용하십시오.

예: G.Edges는 그래프의 간선을 나열하는 테이블을 반환합니다.

예: G.Edges.Weight는 간선 가중치의 숫자형 벡터를 반환합니다.

예: G.Edges.Weight = [10 20 30 55]'는 그래프에 대해 새 간선 가중치를 지정합니다.

예: G.Edges.NormWeight = G.Edges.Weight/sum(G.Edges.Weight)는 간선의 정규화된 가중치가 포함된 테이블에 새 간선 속성을 추가합니다.

데이터형: table

그래프의 노드로, 테이블로 반환됩니다. 기본적으로 비어 있는 N×0 테이블이며, 여기서 N은 그래프의 노드 개수입니다.

  • 그래프에 새 노드 속성을 추가하려면 Nodes 테이블에 새 변수를 생성하십시오.

  • 그래프에 노드를 추가하려면 addnode 객체 함수를 사용하고 제거하려면 rmnode 객체 함수를 사용하십시오.

예: G.Nodes는 그래프의 노드 속성을 나열하는 테이블을 반환합니다. 이 테이블은 기본적으로 비어 있습니다.

예: G.Nodes.Names = {'Montana', 'New York', 'Washington', 'California'}'Nodes 테이블에 변수 Names를 추가하여 그래프에 노드 이름을 추가합니다.

예: G.Nodes.WiFi = logical([1 0 0 1 1]')은 변수 WiFiNodes 테이블에 추가합니다. 이 속성은 특정 공항에서 무선 인터넷을 사용할 수 있음을 지정합니다.

데이터형: table

객체 함수

모두 확장

addedge그래프에 새 간선 추가
rmedge그래프에서 간선 제거
addnode그래프에 새 노드 추가
rmnode그래프에서 노드 제거
findedge그래프에서 간선 찾기
findnode그래프에서 노드 찾기
numedges그래프의 간선 개수
numnodes그래프의 노드 개수
edgecount두 노드 사이의 간선 개수
reordernodes그래프 노드 다시 정렬
subgraph부분 그래프(Subgraph) 추출
centrality노드 중요도 측정
conncomp그래프의 연결성분(Connected Component)
biconncomp그래프의 이중 연결성분(Biconnected Component)
bctree블록-절단 트리(Block-Cut Tree) 그래프
isisomorphic두 그래프가 동형인지 확인
isomorphism두 그래프 간의 동형사상 계산
ismultigraph그래프에 다중 간선이 있는지 여부 확인
simplify다중 그래프를 단순 그래프(simple graph)로 만들기
bfsearch너비 우선 그래프 탐색(Breadth-first Graph Search)
dfsearch깊이 우선 그래프 탐색(Depth-first Graph Search)
shortestpath두 단일 노드 사이의 최단 경로
shortestpathtree노드의 최단 경로 트리
distances모든 노드 쌍의 최단 경로 거리
maxflow그래프의 최대 흐름(Maximum Flow)
minspantree그래프의 최소 신장 트리(Minimum Spanning Tree)
allpathsFind all paths between two graph nodes
hascyclesDetermine whether graph contains cycles
allcyclesFind all cycles in graph
cyclebasisFundamental cycle basis of graph
adjacency그래프 인접 행렬(Adjacency Matrix)
incidence그래프 결합 행렬(Incidence Matrix)
laplacian그래프 라플라시안 행렬(Laplacian Matrix)
degree그래프 노드의 차수
neighbors그래프 노드의 근방
nearest반지름 내 최근접이웃
outedges노드의 진출 간선
plot그래프 노드와 간선 플로팅하기

예제

모두 축소

3개의 노드와 2개의 간선이 있는 graph 객체를 생성합니다. 간선 하나는 노드 1과 노드 2 사이에 있고, 다른 간선은 노드 1과 노드 3 사이에 있습니다.

G = graph([1 1],[2 3])
G = 
  graph with properties:

    Edges: [2x1 table]
    Nodes: [3x0 table]

그래프의 간선 테이블을 확인합니다.

G.Edges
ans=2×1 table
    EndNodes
    ________

     1    2 
     1    3 

그래프에 노드 이름을 추가한 후 새 노드와 간선 테이블을 확인합니다. 각 간선의 끝 노드가 이제 해당 노드 이름을 사용하여 표현됩니다.

G.Nodes.Name = {'A' 'B' 'C'}';
G.Nodes
ans=3×1 table
    Name 
    _____

    {'A'}
    {'B'}
    {'C'}

G.Edges
ans=2×1 table
       EndNodes   
    ______________

    {'A'}    {'B'}
    {'A'}    {'C'}

Nodes 테이블과 Edges 테이블에 추가 변수를 추가하거나 수정하여 그래프 노드나 간선의 특성을 설명할 수 있습니다. 그러나, 이러한 테이블을 수정하여 그래프의 노드나 간선의 개수를 직접 변경할 수는 없습니다. 대신, addedge, rmedge, addnode, rmnode 함수 등을 사용하여 그래프의 노드나 간선 개수를 수정할 수 있습니다.

예를 들어, 노드 2와 노드 3 사이의 그래프에 간선을 추가하고 새 간선 목록을 확인합니다.

G = addedge(G,2,3)
G = 
  graph with properties:

    Edges: [3x1 table]
    Nodes: [3x1 table]

G.Edges
ans=3×1 table
       EndNodes   
    ______________

    {'A'}    {'B'}
    {'A'}    {'C'}
    {'B'}    {'C'}

차수가 4인 완전 그래프를 생성하는 대칭 인접 행렬 A를 만듭니다. 가중치 없이 그래프를 생성하려면 논리형 인접 행렬을 사용하십시오.

A = ones(4) - diag([1 1 1 1])
A = 4×4

     0     1     1     1
     1     0     1     1
     1     1     0     1
     1     1     1     0

G = graph(A~=0)
G = 
  graph with properties:

    Edges: [6x1 table]
    Nodes: [4x0 table]

그래프의 간선 목록을 확인합니다.

G.Edges
ans=6×1 table
    EndNodes
    ________

     1    2 
     1    3 
     1    4 
     2    3 
     2    4 
     3    4 

상부 삼각 인접 행렬을 생성합니다.

A = triu(magic(4))
A = 4×4

    16     2     3    13
     0    11    10     8
     0     0     6    12
     0     0     0     1

인접 행렬을 사용하여 명명된 노드가 있는 그래프를 생성합니다. 'omitselfloops'를 지정하여 A의 대각선에 있는 항목을 무시하고, type'upper'로 지정하여 A가 상부 삼각임을 나타냅니다.

names = {'alpha' 'beta' 'gamma' 'delta'};
G = graph(A,names,'upper','omitselfloops')
G = 
  graph with properties:

    Edges: [6x2 table]
    Nodes: [4x1 table]

간선 정보와 노드 정보를 확인합니다.

G.Edges
ans=6×2 table
           EndNodes           Weight
    ______________________    ______

    {'alpha'}    {'beta' }       2  
    {'alpha'}    {'gamma'}       3  
    {'alpha'}    {'delta'}      13  
    {'beta' }    {'gamma'}      10  
    {'beta' }    {'delta'}       8  
    {'gamma'}    {'delta'}      12  

G.Nodes
ans=4×1 table
      Name   
    _________

    {'alpha'}
    {'beta' }
    {'gamma'}
    {'delta'}

각 간선의 끝 노드 목록을 사용하여 정육면체 그래프를 생성하고 플로팅합니다.

s = [1 1 1 2 2 3 3 4 5 5 6 7];
t = [2 4 8 3 7 4 6 5 6 8 7 8];
G = graph(s,t)
G = 
  graph with properties:

    Edges: [12x1 table]
    Nodes: [8x0 table]

plot(G)

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

각 간선의 끝 노드 목록을 사용하여 정육면체 그래프를 생성하고 플로팅합니다. 별도의 입력값으로 노드 이름과 간선 가중치를 지정합니다.

s = [1 1 1 2 2 3 3 4 5 5 6 7];
t = [2 4 8 3 7 4 6 5 6 8 7 8];
weights = [10 10 1 10 1 10 1 1 12 12 12 12];
names = {'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H'};
G = graph(s,t,weights,names)
G = 
  graph with properties:

    Edges: [12x2 table]
    Nodes: [8x1 table]

plot(G,'EdgeLabel',G.Edges.Weight)

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

각 간선의 끝 노드 목록을 사용하여 가중 그래프(Weighted Graph)를 생성합니다. 그래프에 총 10개의 노드가 포함되어야 함을 지정합니다.

s = [1 1 1 1 1];
t = [2 3 4 5 6];
weights = [5 5 5 6 9];
G = graph(s,t,weights,10)
G = 
  graph with properties:

    Edges: [5x2 table]
    Nodes: [10x0 table]

그래프를 플로팅합니다. 추가 노드는 주 연결성분과 연결되어 있지 않습니다.

plot(G)

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

빈 graph 객체 G를 생성합니다.

G = graph;

그래프에 3개의 노드와 3개의 간선을 추가합니다. st에 대응하는 항목은 그래프 간선의 끝 노드를 정의합니다. addedge는 그래프에 적절한 노드가 아직 없는 경우 자동으로 추가합니다.

s = [1 2 1];
t = [2 3 3];
G = addedge(G,s,t)
G = 
  graph with properties:

    Edges: [3x1 table]
    Nodes: [3x0 table]

간선 목록을 확인합니다. 각 행은 그래프의 간선을 설명합니다.

G.Edges
ans=3×1 table
    EndNodes
    ________

     1    2 
     1    3 
     2    3 

최적의 성능을 구현하려면 graph에 대한 단일 호출을 사용하여 그래프를 한 번에 모두 생성하십시오. 루프에 노드나 간선을 추가하면 큰 그래프의 경우 속도가 느려질 수 있습니다.

변수 EndNodes, Weight, Code가 포함된 간선 테이블을 만듭니다. 그런 다음 변수 NameCountry가 포함된 노드 테이블을 만듭니다. 각 테이블의 변수는 그래프 노드와 간선의 속성을 지정합니다.

s = [1 1 1 2 3];
t = [2 3 4 3 4];
weights = [6 6.5 7 11.5 17]';
code = {'1/44' '1/49' '1/33' '44/49' '49/33'}';
EdgeTable = table([s' t'],weights,code, ...
    'VariableNames',{'EndNodes' 'Weight' 'Code'})
EdgeTable=5×3 table
    EndNodes    Weight      Code   
    ________    ______    _________

     1    2         6     {'1/44' }
     1    3       6.5     {'1/49' }
     1    4         7     {'1/33' }
     2    3      11.5     {'44/49'}
     3    4        17     {'49/33'}

names = {'USA' 'GBR' 'DEU' 'FRA'}';
country_code = {'1' '44' '49' '33'}';
NodeTable = table(names,country_code,'VariableNames',{'Name' 'Country'})
NodeTable=4×2 table
     Name      Country
    _______    _______

    {'USA'}    {'1' } 
    {'GBR'}    {'44'} 
    {'DEU'}    {'49'} 
    {'FRA'}    {'33'} 

노드 테이블과 간선 테이블을 사용하여 그래프를 생성합니다. 노드 레이블과 간선 레이블로 국가 코드를 사용하여 그래프를 플로팅합니다.

G = graph(EdgeTable,NodeTable);
plot(G,'NodeLabel',G.Nodes.Country,'EdgeLabel',G.Edges.Code)

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

확장 기능

스레드 기반 환경
MATLAB®의 backgroundPool을 사용해 백그라운드에서 코드를 실행하거나 Parallel Computing Toolbox™의 ThreadPool을 사용해 코드 실행 속도를 높일 수 있습니다.

버전 내역

R2015b에 개발됨

모두 확장