[자료구조] : 그래프 용어정리(C)

지환·2022년 5월 11일

자료구조

목록 보기

26/38

graph

그래프란 일련의 노드(node, vertex, 정점, 꼭지점) 집합 V와 엣지(edge, 간선, 변) 집합 E로 구성된 자료구조의 일종입니다. 일반적으로 노드엔 데이터, 엣지엔 노드와 노드 사이의 관계 정보가 포함되어 있습니다. 이를 그림으로 나타내면 다음과 같습니다.

sparse/dense graph

sparse graph란 하단 좌측 그림처럼 노드의 수보다 엣지 수가 적은 그래프를 가리킵니다. 반대로 dense graph란 하단 우측 그림처럼 노드 수보다 엣지 수가 큰 그래프입니다.

incident/adjacent

임의의 두 노드가 하나의 엣지로 연결돼 있을 경우, 이 노드들은 서로 인접(adjacent)해 있다고 합니다. 같은 경우에 이 엣지는 두 노드에 부속(incident)한다고 합니다.

degree

한 노드의 차수(degree)란 해당 노드에 연결된 엣지의 수(혹은 엣지 가중치의 합)를 가리킵니다.

loop/isolated

다음 그림과 같이 한 엣지가 같은 노드에 부속해 있을 때 loop이라고 합니다.

이와 반대로 임의의 한 노드에 부속해 있는 엣지가 전혀 없을 때 해당 노드를 isolated vertex라고 합니다.

isomorphic

한 그래프의 두 노드를 연결하는 엣지가 하나이고, 다른 그래프에서 그에 대응하는 노드를 연결하는 엣지가 하나뿐일 때 두 그래프는 동형(同型, isomorphic)이라고 합니다. 쉽게 말해 두 그래프는 생김새만 다르게 생길 뿐 본질적으로는 구조가 같다는 이야기입니다. 다음 그림과 같습니다.

subgraph

임의의 그래프 G=(V,E)가 주어졌을 때 다음을 만족하는 G′=(V′,E′)는 G의 부분그래프(subgraph)라고 합니다.

E′는 V′에만 부속(=V′에 속한 모든 엣지가 G′에 있어야 함)되어 있으며 E의 부분집합이다.
V′는 V의 부분집합이다.

이 가운데 V=V′를 만족하는 부분그래프를 spanning subgraph라고 합니다. 쉽게 말해 원 그래프와 노드는 같고 일부 엣지만 포함된 부분그래프를 가리킵니다. 이 부분그래프가 트리을 만족할 경우 spanning tree라고 합니다. 하단 좌측과 우측의 그림이 원 그래프와 spanning subgraph를 예로 든 것입니다.

complete graph/multigraph

모든 노드들이 엣지로 연결돼 있어 엣지의 수가 최대인 그래프(하단 좌측)를 완전그래프(complete graph)라고 합니다. 노드 수가 4개라면 기호로 K4라고 표시합니다. 반면 노드 사이를 잇는 엣지가 하나 이상일 경우 해당 엣지를 transitive하다고 하며, 이 그래프를 multigraph라고 합니다(하단 우측).

weighted graph

가중치그래프(weighted graph)란 엣지에 가중치 내지 우선순위 정보가 추가된 형태의 그래프입니다. 이 때 함수 g는 엣지를 가중치로 매핑하는 역할을 합니다.

물론 방향그래프 또한 가중치를 가질 수 있습니다. 이글 방향가중치그래프(directed weighted graph)라고 합니다.

path

그래프에서 경로(path)란 인접한 노드들로 구성된 시퀀스(1개 이상)를 가리킵니다. 엣지가 겹치지 않는 경로를 simple하다고 하고, 노드가 겹치지 않는 경로를 elementary하다고 합니다. 경로의 길이(length)는 경로 내 존재하는 엣지의 수를 나타냅니다. 다음과 같은 그래프의 노드 시퀀스가 있다고 칩시다

[v1,v2,v3,v4,v5,v3,v4,v5]
[v1,v2,v3,v4,v5,v8,v6,v4,v7]

위 예시에서 첫번째 노드 시퀀스는 인접한 노드들로 구성돼 있기 때문에 경로라고 할 수 있습니다. 그러나 엣지도, 노드도 겹치기 때문에 simple하지도, elementary하지도 않습니다.

두번째 노드 시퀀스는 인접한 노드들로 구성돼 있기 때문에 경로라고 할 수 있습니다. 엣지가 겹치지 않기 때문에 simple하다고 말할 수 있습니다. 하지만 노드가 겹치기 때문에 elementary하지는 않습니다.

cycle

사이클(cycle)이란 한 노드에서 시작해 해당 노드에서 끝나는 경로를 가리킵니다. 사이클(cycle) 또한 엣지가 겹치지 않는 경우 simple하다고 하고, 노드가 겹치지 않을 경우 elementary하다고 합니다. 위 그래프를 기준으로 아래의 두 개 노드 시퀀스를 보겠습니다.

[v1,v2,v3,v4,v5,v8,v6,v5,v9,v1]
[v1,v2,v3,v4,v5,v9,v1]

첫번째 노드 시퀀스는 인접한 노드들로 구성돼 있고 v1으로 시작해 v1으로 끝났으므로 사이클입니다. 엣지가 겹치지 않기 때문에 simple하다고 말할 수 있습니다. 하지만 노드가 겹치기 때문에 elementary하지는 않습니다.

두번째 노드 시퀀스는 인접한 노드들로 구성돼 있고 v1으로 시작해 v1으로 끝났으므로 사이클입니다. 엣지도, 노드도 겹치지 않기 때문에 각각 simple하고, elementary하다고 말할 수 있습니다.

만약 n개의 노드가 사이클을 이루고 있을 경우 이를 기호로 Cn이라고 표시합니다. 다음 그림과 같이 사이클이 없는 그래프를 acyclic하다고 합니다.

connected

임의의 두 노드가 연결되었다(connected)는 것은 두 노드 사이에 경로가 존재한다는 이야기입니다. 이와 관련해 다음과 같이 정의됩니다.

모든 노드쌍 사이에 경로가 존재하는 무방향그래프는 연결되었다고 말한다.
임의의 방향그래프에서 방향을 무시하고 보면 연결되어 있을 경우, 해당 방향 그래프는 연결되었다고 말한다.
방향그래프의 임의의 노드쌍 a, b에 대해 a에서 b로 가는 경로, b에서 a로 가는 경로가 존재한다면, 해당 방향그래프는 강연결(strongly connected)되었다고 말한다.

아래 방향그래프에서 방향을 무시하고 보면 이 그래프 내 임의의 노드쌍 사이에 모두 경로가 존재함을 알 수 있습니다. 따라서 아래 방향그래프는 connected graph입니다. 하지만 v1에서 v3로 가는 경로는 존재(v1,v2,v3,v9,v3)하나, 반대로 v3에서 v1으로 가는 경로는 존재하지 않는다는 점에서 strongly conntected graph는 아닙니다.

connected component

원 그래프 G에서 노드와 엣지가 서로 겹치지 않는(independent) 부그래프를 G의 요소(component)라고 합니다. 이들 요소 가운데 요소 내 모든 노드쌍에 대해 경로가 존재하는 부그래프 S를 G의 연결요소(connected component)라고 합니다. 그 정의상 연결그래프(connected graph)는 하나의 연결요소만을 가집니다.

원 그래프의 부분그래프들 사이에 겹치는 요소가 없고, 부분그래프의 합집합이 원 그래프를 이룰 때 이들 부분그래프를 파티션(partition)이라고 합니다. 아래 그림에서 15개 노드와 모든 엣지를 G로 본다면 G의 연결요소는 두 개이며, 이 연결요소는 G의 파티션입니다.

연결요소 가운데 노드 수가 가장 많은 연결요소를 최대연결요소(maximal connected component)라고 합니다.

Vertex/edge-cut

원그래프에서 어떤 노드를 제거해 부분그래프로 나누는 것을 vertex-cut이라고 합니다. 엣지를 제거해 부분그래프로 나누는 과정을 edge-cut이라고 합니다. 아래 예시에서 노드 e를 제거하면 vetex-cut, 노드 e와 노드 x를 잇는 엣지를 제거하면 원그래프가 두 개 부분그래프로 분리되면서 각각 vetex-cut, edge-cut이 됩니다.

가중치무방향그래프에서 제거 대상 엣지의 가중치가 최대가 되도록 하는 edge-cut 기법을 MaxCut, 최소로 하는 기법을 MinCut이라고 합니다.

Join

새로운 노드 X가 추가돼 기존 그래프 V의 모든 노드와 연결될 경우 조인(Join)이라고 합니다. 이때 기호로는 V+X라고 표기합니다.

edge complement

다음과 같은 관계를 지니는 두 그래프를 edge complement라고 합니다. 노드는 서로 같고 엣지 존재 양상이 정반대인 경우에 해당합니다.

releative complement

아래 그림과 같이 H는 G의 부그래프이고, H에 속한 모든 엣지를 제거한 그래프를 relative complement라고 합니다. 기호로는 G−H라고 씁니다.

graph representation

그래프를 컴퓨터가 처리하게 만드려면, 그래프를 적절한 자료구조로 변환해 주어야 합니다. 크게 두 가지 방식이 있는데요. 인접행렬(adjacency matrix)과 인접리스트(adjacency list)입니다. 각각 행렬과 연결리스트(linked list)로 구현합니다.

가중치가 없는 방향그래프를 인접행렬로 표현하는 방식을 도식화한 그림은 다음과 같습니다.