그래프 이론 용어

그래프 이론에서 사용하는 많은 용어들에 대해서 정리한다. 그래프 이론은 오랫동안 연구되어 왔고 지금도 활발하게 연구되고 있기 때문에 그래프 이론에서 사용하는 모든 용어를 일목요연하게 완벽히 정리하기는 사실상 불가능하다. 여기에 정리한 내용은 그래프 이론과 관련한 기본적인 내용만을 포함한 것이며, 자세한 내용은 관련 교과서를 참고해야 한다.

무향 그래프의 기본 정의

6개의 꼭짓점 7개의 변을 가지는 그래프. 6번 꼭짓점의 차수는 1이고, 5번 꼭짓점의 차수는 3이다.

그래프는 꼭짓점(영어: vertex, node)과 변(邊, 영어: edge, link, line, 간선)으로 이루어져 있다. 꼭짓점의 차수(次數, 영어: degree)는 그 꼭짓점에 연결되어 있는 변의 개수이다. 유향 그래프와 구별하기 위하여, "무향 그래프"로 부르기도 한다.

• 차수(영어: degree): 한 꼭짓점에 이어져 있는 변의 수.
• 인접(영어: adjacent) 두 개의 꼭짓점 사이에 변이 존재한다면, 이 두 꼭짓점들이 인접한다고 한다.

유향 그래프의 기본 정의

유향 그래프의 경우, 다음과 같은 용어를 사용한다.

• 입력 차수(入力次數, 영어: in-degree): 한 꼭짓점으로 들어오는 변의 개수
• 출력 차수(出力次數, 영어: out-degree): 한 꼭짓점에서 나가는 변의 개수

보행의 종류

여기서 그래프는 무향 그래프로 간주한다. 유향 그래프의 경우 이들 용어들은 방향을 준수하여야 한다.

• 보행(영어: walk 워크^[*]): 꼭짓점과 변이 교대로 나타나는 열(sequence)이면서, 각 변의 앞과 뒤에 위치한 꼭짓점을 그 변의 양끝점으로 갖는 열
• 트레일(영어: trail): 변이 중복되지 않는 보행
• 경로(영어: path 패스^[*]): 꼭짓점이 중복되지 않는 트레일. 이는 변과 꼭짓점이 모두 중복되지 않는 보행과 같다.
• 닫힌 보행(영어: closed walk)은 시작점과 끝점이 같은 보행이다. 마찬가지로 닫힌 트레일을 정의한다. 닫힌 경로는 순환(영어: cycle 사이클^[*])이라고 한다. 일부 저자들은 닫힌 트레일을 회로(영어: circuit) 또는 여행(영어: tour 투어^[*])이라고 한다.

즉, 꼭짓점 $v_{0},v_{1},\dots ,v_{n}$으로 구성된 보행은 성질에 따라서 다음과 같이 분류된다. (꼭짓점이 겹칠 수 없다면, 물론 변 또한 겹칠 수 없다.)

용어	$v_{0}=v_{n}$	변이 겹칠 수 없음	꼭짓점이 겹칠 수 없음
보행	×	×	×
트레일	×	○	×
경로	×	○	○
닫힌 보행	○	×	×
닫힌 트레일	○	○	×
순환	○	○	○

그래프 전체를 거치는 보행

• 오일러 트레일(영어: Eulerian trail): 모든 변이 정확히 한 번씩 포함된 닫힌 트레일. "오일러 경로"라고도 하나, 이는 일반적으로 경로가 아니다 (즉, 꼭짓점이 중복될 수 있다).
• 해밀턴 경로(영어: Hamiltonian path): 모든 꼭짓점을 정확히 한 번씩 거치는 경로. 만약 시작점과 끝점이 같다면, 해밀턴 순환(영어: Hamiltonian cycle)이라고 한다.

부분 그래프의 종류

• 부분 그래프(영어: subgraph 서브그래프^[*]) - 어떤 그래프의 꼭짓점 집합의 부분집합과 그에 속한 변으로 이루어진 그래프. 혹은 어떤 그래프의 변 집합의 부분집합과 그에 속한 꼭짓점으로 이루어진 그래프
• (어떤 속성에 대한) 최대 부분 그래프(maximal subgraph with regard to a property): 부분 그래프가 그 속성을 유지하고 다른 꼭짓점이나 변이 그 부분 그래프에 첨가되면 그 속성을 유지하지 못하는 부분 그래프

중요한 부분 그래프의 예로는 다음을 들 수 있다.

• 클릭(영어: clique)
• 생성나무(영어: spanning tree)

위상수학적 성질

무향 그래프는 세포 복합체로서, 자연스럽게 위상 공간의 구조를 갖는다. 따라서 위상수학적 용어를 적용할 수 있다.

• 연결 그래프(영어: connected graph): 어떤 그래프에 속한 임의의 두 꼭짓점에 대해 각 꼭짓점을 양 끝점으로 하는 경로가 존재할 경우, 그 그래프를 연결된 그래프라고 한다. 즉, 세포 복합체로 간주하였을 때, 연결 공간인 것이다.
  • 비연결 그래프(영어: disconnected graph): 연결되어 있지 않은 그래프
  • 연결 성분(영어: (connected) component): 어떤 그래프의 연결 속성에 대한 최대 부분 그래프. 이는 세포 복합체로 간주하였을 때, 일반위상수학에서의 연결 성분과 같다.
• 오일러 지표(영어: Euler characteristic) 및 호몰로지 역시 세포 복합체로 여겨 정의할 수 있다. 물론, 이 경우 $H_{0}$과 $H_{1}$만이 존재한다. 오일러 지표가 $\chi =2-2g$라면, $g$를 종수(영어: genus)라고 한다. 종수가 0인 그래프를 평면 그래프라고 한다.

그래프의 크기의 척도

• 두 꼭짓점 $v_{1}$, $v_{2}$ 사이의 거리(영어: distance)는 $v_{1}$, $v_{2}$ 사이의 경로 가운데 가장 짧은 것의 변의 수이다. 이러한 경로가 존재하지 않는다면 길이는 무한대이다.
• 이심률(영어: eccentricity): 한 꼭짓점에서 다른 모든 꼭짓점 사이의 거리들 중 가장 큰 거리
• 지름(영어: diameter): 그래프의 최대 이심률
• 가중 그래프(영어: weighted graph)는 정점이나 변에 무게가 할당된 그래프이다. 즉, 정점 가중 그래프는 정점에 무게가 있으며 변 가중 그래프는 변에 무게가 있다.

같이 보기

• 그래프 이론

외부 링크

• (한국어) 그래프 이론 용어사전
• (영어) Wasserman, Stanley and Faust, Katherine. Social Network Analysis. Cambridge University Press. NY:1994.