그래프 ( graph in computer science )

주제(Subject)
--------------------------------------------------------
한글(약어) : 그래프()
영어(약어) : graph()


관련개념(Related Concepts)
--------------------------------------------------------
자료구조(Information Structure)
트리(Tree)


개요(Summary)
--------------------------------------------------------
정점(V)과 간선(E)의 집합으로 구성됨. G = ( V , E )


본문(Body)
--------------------------------------------------------
1. 종류
   (1) 방향을 가지는지 여부에 따라서
      1) 방향그래프
      2) 무방향그래프

2. 개념 정리
   (1) 인접(adjacent)
      그래프 G에 간선 (u,v)가 있을 때, 정점 u와 v는 인접해 있다고 한다.

   (2) 부수(incident)
      그래프 G에 간선 (u,v)가 있을 때, 간선은 정점 u와 v에 부수되어 있다고 한다.

   (3) 차수(degree)
      무방향그래프에서는 정점에 부수된 간선의 개수
      방향그래프에서는 간선의 외향,내향에 따라 차수를 구별하여 외향차수, 내향차수라 한다

   (4) 경로(path)
      간선으로 연결된 정점들의 순열

   (5) 길이(depth)
      경로상에 존재하는 간선의 개수

   (6) 도달가능(reachable)
      정점 u에서 v까지 경로 p가 존재할 경우 "도달가능"하다고 한다.

   (7) 사이클(cycle)
      시작정점과 끝정점이 같은 간선

   (8) 부분그래프(subgraph)
      그래프 G'의 모든 간선과 정점이 그래프 G의 부분집합일 경우, G'를 G의 부분그래프라 한다.

   (9) 완전그래프(complete graph)
      모든 정점들이 간선으로 연결된 그래프.

   (10) 이분그래프(bipartite graph)
      모든 정점의 집합을 서로 소인 V1, V2로 나눌 때, V1집합 내부간의 간선은 존재하지 않고, V2집합 내부간 간선도 존재하지 않으며, 모든 간선이 V1집합과 V2집합만을 연결하는 그래프

   (11) 숲(forest)
      무사이클, 무방향 그래프

   (12) 나무(tree)
      연결된 무사이클, 무방향 그래프


모임,단체(Commutities)
--------------------------------------------------------


블로그,개인 홈페이지 등(Humanities)
--------------------------------------------------------
1. Dr. Christopher P. Mawata (Department of Mathematics, University of Tennessee at Chattanooga )
   http://oneweb.utc.edu/~Christopher-Mawata


참고문서(References)
--------------------------------------------------------
* 한국어(Korean)
저자. 역자. "제목". 출판사. 출판년도. (ISBN:)
1. 조유근, 홍영식, 이지수, 김명. "알고리즘 - 알고리즘의 설계와 분석". 이한출판사. 2005. (ISBN:89-8241-210-7)


* 영어(English)
저자. 제목, 판, 출판사. 출판년도. (ISBN:)
1. Wikipedia : Graph theory
   http://en.wikipedia.org/wiki/Graph_theory

2. Graph Theory Lessons
   http://oneweb.utc.edu/~Christopher-Mawata/petersen/index.htm