그래프 이론에서 사용하는 많은 용어들에 대해서 정리한다. 그래프 이론은 오랫동안 연구되어 왔고 지금도 활발하게 연구되고 있기 때문에 그래프 이론에서 사용하는 모든 용어를 일목요연하게 완벽히 정리하기는 사실상 불가능하다. 여기에 정리한 내용은 그래프 이론과 관련한 기본적인 내용만을 포함한 것이며, 자세한 내용은 관련 교과서를 참고해야 한다.
6개의 꼭짓점 7개의 변을 가지는 그래프. 6번 꼭짓점의 차수는 1이고, 5번 꼭짓점의 차수는 3이다.
그래프는 꼭짓점(영어:vertex, node)과 변(邊, 영어:edge, link, line, 간선)으로 이루어져 있다. 꼭짓점의 차수(次數, 영어:degree)는 그 꼭짓점에 연결되어 있는 변의 개수이다. 유향 그래프와 구별하기 위하여, "무향 그래프"로 부르기도 한다.
경로(영어:path패스[*]): 꼭짓점이 중복되지 않는 트레일. 이는 변과 꼭짓점이 모두 중복되지 않는 보행과 같다.
닫힌 보행(영어:closed walk)은 시작점과 끝점이 같은 보행이다. 마찬가지로 닫힌 트레일을 정의한다. 닫힌 경로는 순환(영어:cycle사이클[*])이라고 한다. 일부 저자들은 닫힌 트레일을 회로(영어:circuit) 또는 여행(영어:tour투어[*])이라고 한다.
즉, 꼭짓점 으로 구성된 보행은 성질에 따라서 다음과 같이 분류된다. (꼭짓점이 겹칠 수 없다면, 물론 변 또한 겹칠 수 없다.)
자세한 정보 ...
용어
변이 겹칠 수 없음
꼭짓점이 겹칠 수 없음
보행
×
×
×
트레일
×
○
×
경로
×
○
○
닫힌 보행
○
×
×
닫힌 트레일
○
○
×
순환
○
○
○
닫기
그래프 전체를 거치는 보행
오일러 트레일(영어:Eulerian trail): 모든 변이 정확히 한 번씩 포함된 닫힌 트레일. "오일러 경로"라고도 하나, 이는 일반적으로 경로가 아니다 (즉, 꼭짓점이 중복될 수 있다).
해밀턴 경로(영어:Hamiltonian path): 모든 꼭짓점을 정확히 한 번씩 거치는 경로. 만약 시작점과 끝점이 같다면, 해밀턴 순환(영어:Hamiltonian cycle)이라고 한다.
부분 그래프(영어:subgraph서브그래프[*]) - 어떤 그래프의 꼭짓점 집합의 부분집합과 그에 속한 변으로 이루어진 그래프. 혹은 어떤 그래프의 변 집합의 부분집합과 그에 속한 꼭짓점으로 이루어진 그래프
(어떤 속성에 대한) 최대 부분 그래프(maximal subgraph with regard to a property): 부분 그래프가 그 속성을 유지하고 다른 꼭짓점이나 변이 그 부분 그래프에 첨가되면 그 속성을 유지하지 못하는 부분 그래프