잔글 (문자열 찾아 바꾸기 - "{{학술 관련 정보}}" 문자열을 "" 문자열로) |
잔글편집 요약 없음 |
||
9번째 줄: | 9번째 줄: | ||
을 만족하면 ''G''를 '''그래프'''라고 한다. | 을 만족하면 ''G''를 '''그래프'''라고 한다. | ||
이때 ''V''의 원소를 '''꼭짓점(vertex)''', ''E''의 원소를 ''' | 이때 ''V''의 원소를 '''꼭짓점(vertex)''', ''E''의 원소를 '''변(edge)'''이라고 한다. | ||
''E''는 집합이기는 하지만 같은 {''u'',''v''}가 여럿 있는 것도 허용하며, 이러한 모서리를 '''다중 | ''E''는 집합이기는 하지만 같은 {''u'',''v''}가 여럿 있는 것도 허용하며, 이러한 모서리를 '''다중 변'''(multiple edges) 또는 '''평행 변'''(parallel edges)이라고 한다. 또, ''u''=''v''인 경우는 '''고리(loop)'''라고 한다. | ||
== 그래프 알고리즘 == | == 그래프 알고리즘 == |
2017년 11월 12일 (일) 15:21 판
정의
그래프(Graph)는 꼭짓점과 모서리로만 이루어진 도형이다.
자세히 말해, 순서쌍 [math]\displaystyle{ G=(V,E) }[/math]가 다음 두 조건
- V는 공집합이 아닌 유한집합이다.
- E는 [math]\displaystyle{ \{u,v\}\;(u,v\in V) }[/math]들의 모임인 유한집합이다.
을 만족하면 G를 그래프라고 한다.
이때 V의 원소를 꼭짓점(vertex), E의 원소를 변(edge)이라고 한다.
E는 집합이기는 하지만 같은 {u,v}가 여럿 있는 것도 허용하며, 이러한 모서리를 다중 변(multiple edges) 또는 평행 변(parallel edges)이라고 한다. 또, u=v인 경우는 고리(loop)라고 한다.