C로 만드는 자료구조 - 그래프 관련 용어

dsbook.tistory.com/280  (이전글)

C로 만드는 자료구조 - 그래프(Graph)란?

그래프 관련 용어들

그래프를 실제 규현하고 그래프 기반의 다양한 알고리즘을 살펴보기 전에 그래프와 관련된 용어들을 알아보자.

인접(Adjacent)

두 개의 노드를 연결하는 간선이 존재하는 경우 두 노드는 인접(Adjacent)되었다고 한다.

다음 그림을 통해 자세히 살펴보자.

부속(Incident)

두 개의 노드를 연결하는 간선이 존재하는 경우 이 간선은 두 노드에 각각 부속(Incident) 되었다고 한다.

 

차수(Degree)

노드에 부속된 간선의 개수를 차수(Degree)라 한다. 아래 왼쪽 그림의 무방향 그래프에서는 노드단 방향 그래프의 경우에는 노드로 들어오는 간선의 개수를 진입차수(In-degree), 노드에서 나가는 간선의 개수를 진출차수(Out-degree)라 한다.

경로(Path)

두 노드 A에서 노드 B까지의 경로 (Path)는 노드 A에서 노드 B에 이르는 간선들의 인접 노드를 순서대로 나열한 리스트를 말한다.

다음 그림을 통해 자세히 살펴보자. 아래 그림은 노드 1에서 노드 4까지 가는 경로 4가지 경우를 나타낸 것이다.

위 그림에서 경로길이는 차례대로 4,5,5,6이 된다.

 경로 중 중복되는 노드가 없는 경우를 단순경로(Simple Path), 보통 방향 그래프에서의 단순 경로는 단순 방향 경로(Simple Directed Path)라 한다. 위 4가지 경로 모두 겹치는 노드가 없기 때문에 단순경로이다. 또한 단순 경로 중에서 경로의 시작 노드와 마지막 노드가 같은 경로를 사이클(Cycle)이라고 한다. 마지막으로, 그래프 내의 모든 노드 사이에 경로가 있을 때 연결되었다(Connected)고 한다.

그래프의 동일성

2개의 서로 다른 그래프가 서로 같은지 판단하는 동일성에 대해 알아보자.

다음 그림에서 2개의 그래프 G와 G'은 서로 달라보이지만 사실은 동일한 그래프이다.

루프(Loop)

그래프의 임의의 노드에서 자기 자신으로 이어지는 간선을 루프(Loop)라고 한다.

아래 그림은 루프를 가지는 그래프의 예이다.