그래프 (그래프 이론): 두 판 사이의 차이

2015년 5월 28일 (목) 14: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)라고 한다. 또, u=v인 경우에도 {u,v}라고 적으며, 이러한 모서리를 고리(loop)라고 한다.

그래프 알고리즘

그래프 색칠하기

그래프의 종류

@@ 2번째 줄: / 2번째 줄: @@
 == 정의 ==
 [[파일:defgraph.png|섬네일|다중 모서리와 고리를 가진 그래프]]
-'''그래프(Graph)'''는 꼭짓점과 모서리로 이루어진 도형이다. 자세히 말해, 순서쌍 <math>G=(V,E)</math>가 다음 조건
+'''그래프(Graph)'''는 꼭짓점과 모서리로만 이루어진 도형이다.
-* ''V''는 [[공집합]]이 아닌 유한집합이다.
-* ''E''는 <math>\{u,v\}\;(u,v\in V)</math>들의 모임인 유한집합이다.
+자세히 말해, 순서쌍 <math>G=(V,E)</math>가 다음 두 조건
-을 만족하면 ''G''를 '''그래프'''라고 한다. 이때 ''V''의 원소를 '''꼭짓점(vertex)''', ''E''의 원소를 '''모서리(edge)'''라고 한다. 만약 모서리 ''{u,v}''에 대해 ''u''=''v''이면 '''고리(loop)'''라고 하며, ''{u,v}''가 둘 이상인 경우는 '''다중 모서리(multiple edges)'''라고 한다.
+#''V''는 [[공집합]]이 아닌 유한집합이다.
+#''E''는 <math>\{u,v\}\;(u,v\in V)</math>들의 모임인 유한집합이다.
+을 만족하면 ''G''를 '''그래프'''라고 한다.
+이때 ''V''의 원소를 '''꼭짓점(vertex)''', ''E''의 원소를 '''모서리(edge)'''라고 한다.
+''E''는 집합이기는 하지만 같은 {''u'',''v''}가 여럿 있는 것도 허용하며, 이러한 모서리를 '''다중 모서리(multiple edges)'''라고 한다. 또, ''u''=''v''인 경우에도 {''u'',''v''}라고 적으며, 이러한 모서리를 '''고리(loop)'''라고 한다.
 == 그래프 알고리즘 ==