정의[편집 | 원본 편집]
그래프(graph)는 꼭짓점과 변으로 이루어져 있다.
자세히 말해, 순서쌍 [math]\displaystyle{ G=(V,E) }[/math]가 다음 두 조건
- [math]\displaystyle{ V }[/math]는 공집합이 아닌 유한집합이다. (이 조건은 논의의 편의를 위해 존재하며, 꼭짓점이 무한한 그래프를 다루기도 한다.)
- [math]\displaystyle{ E }[/math]는 '끝점'이 정의되는 변들의 모임이다. 즉, [math]\displaystyle{ e\in E }[/math]에는 함수 [math]\displaystyle{ \partial:~e\mapsto \partial e }[/math]가 있어 [math]\displaystyle{ 1\le |\partial e|\le 2 }[/math]를 만족한다.
을 만족하면 [math]\displaystyle{ G }[/math]를 그래프라고 한다.
이때 [math]\displaystyle{ V }[/math]의 원소를 꼭짓점(vertex), [math]\displaystyle{ E }[/math]의 원소를 변(edge)이라고 한다. [math]\displaystyle{ \partial e = \partial f,~e\ne f }[/math]인 두 변은 다중 변(multiple edges) 또는 평행 변(parallel edges)라고 하며, 또 [math]\displaystyle{ |\partial e|=1 }[/math]인 변을 고리(loop)라고 한다. 평행 변과 고리가 없는 그래프를 단순그래프(simple graph)라고 한다. 책에 따라, 단순그래프를 그래프라고 부르고, 평행 변과 고리를 허용하는 그래프를 다중그래프(multigraph)라고 하기도 한다.