-
그래프의 종류)
그래프는 방향성과 연결 정도에 따라 구분하며 추가로 간선에 가중치를 할당한 그래프가 존재한다.
- 무방향 그래프(Undirected Graph) 두 노드를 연결하는 간선의 방향이 없는 그래프
- 방향 그래프(Directed Graph) 노드를 연결할 때 간선에 방향이 있는 그래프
- 완전 그래프(Complete Graph) 정점이 모두 서로 연결된 그래프
- 부분 그래프(Subgraph) 완전 그래프에서 특정 간선이 제외된 그래프
- 가중 그래프(Weigh Graph) 간선마다 가중치가 할당된 그래프
그래프의 표현)
그래프는 방향성에 따라 다르게 표현된다. 가령 정점 A, B가 존재하는 완전 그래프 G에 대해 다음과 같이 표현한다.
- 무방향 그래프 V(G) = { A, B } E(G) = { (A, B) }
- 방향 그래프 V(G) = { A, B } E(G) = { <A, B>, <B, A> }
예를 들어 아래 그래프에 대해 무방향 그래프와 방향 그래프의 표현은 다음과 같다.
- V(무방향 그래프) = { A, B, C, D } E(무방향 그래프) = { (A, B), (A, D), (B, C), (B, D), (C, D) }
- V(방향 그래프) = { A, B, C, D } E(방향 그래프) = { <A, B>, <A, D>, <B, C>, <B, D>, <C, A>, <C, D>, <D, A> }