잔글편집 요약 없음 |
|||
| (다른 사용자 한 명의 중간 판 3개는 보이지 않습니다) | |||
| 1번째 줄: | 1번째 줄: | ||
== 정의 == | == 정의 == | ||
[[파일:defgraph.png|섬네일|다중 | [[파일:defgraph.png|섬네일|다중 변과 고리를 가진 그래프]] | ||
'''그래프 | '''그래프'''(graph)는 꼭짓점과 변으로 이루어져 있다. | ||
자세히 말해, 순서쌍 <math>G=(V,E)</math>가 다음 두 조건 | 자세히 말해, 순서쌍 <math>G=(V,E)</math>가 다음 두 조건 | ||
# | #<math>V</math>는 [[공집합]]이 아닌 유한집합이다. (이 조건은 논의의 편의를 위해 존재하며, 꼭짓점이 무한한 그래프를 다루기도 한다.) | ||
#''E | #<math>E</math>는 '끝점'이 정의되는 변들의 모임이다. 즉, <math>e\in E</math>에는 함수 <math>\partial:~e\mapsto \partial e</math>가 있어 <math>1\le |\partial e|\le 2</math>를 만족한다. | ||
을 만족하면 | 을 만족하면 <math>G</math>를 '''그래프'''라고 한다. | ||
이때 '' | 이때 <math>V</math>의 원소를 '''꼭짓점'''(vertex), <math>E</math>의 원소를 '''변'''(edge)이라고 한다. <math>\partial e = \partial f,~e\ne f</math>인 두 변은 '''다중 변'''(multiple edges) 또는 '''평행 변'''(parallel edges)라고 하며, 또 <math>|\partial e|=1</math>인 변을 '''고리'''(loop)라고 한다. 평행 변과 고리가 없는 그래프를 '''단순그래프'''(simple graph)라고 한다. 책에 따라, 단순그래프를 그래프라고 부르고, 평행 변과 고리를 허용하는 그래프를 '''다중그래프'''(multigraph)라고 하기도 한다. | ||
== 그래프 알고리즘 == | |||
* [[그래프 탐색]] | |||
* [[네트워크 플로우]] | |||
* [[최소비용 신장 트리]] | |||
* [[최단경로]] | |||
* 부그래프 | |||
** [[클릭]] | |||
** [[강연결요소]] | |||
== 그래프 색칠하기 == | == 그래프 색칠하기 == | ||
| 29번째 줄: | 35번째 줄: | ||
* [[정규그래프]] | * [[정규그래프]] | ||
[[분류:그래프 이론]] | [[분류:그래프 이론]] | ||
2017년 11월 15일 (수) 00:18 기준 최신판
정의[편집 | 원본 편집]
그래프(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)라고 하기도 한다.