< 페미위키:포크 프로젝트 | 리브레 위키
정의
그래프(graph)는 꼭짓점과 변으로 이루어져 있다.
자세히 말해, 순서쌍 가 다음 두 조건
- 는 공집합이 아닌 유한집합이다. (이 조건은 논의의 편의를 위해 존재하며, 꼭짓점이 무한한 그래프를 다루기도 한다.)
- 는 '끝점'이 정의되는 변들의 모임이다. 즉, 에는 함수 가 있어 를 만족한다.
을 만족하면 를 그래프라고 한다.
이때 의 원소를 꼭짓점(vertex), 의 원소를 변(edge)이라고 한다. 인 두 변은 다중 변(multiple edges) 또는 평행 변(parallel edges)라고 하며, 또 인 변을 고리(loop)라고 한다. 평행 변과 고리가 없는 그래프를 단순그래프(simple graph)라고 한다. 책에 따라, 단순그래프를 그래프라고 부르고, 평행 변과 고리를 허용하는 그래프를 다중그래프(multigraph)라고 하기도 한다.
