[Data Structure] 그래프 정의/용어

그래프 (Graph)

G = (V, E)

- 정점(Vertex), 간선(Edge)들의 집합으로 구성

- 정점, 간선 모두 데이터 저장 가능

 

• Vertex : V(G) = { 1, 2, 3, 4, 5 }
• Edge : E(G) = { (1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5) }

 

 

그래프의 종류

▶ 무방향 그래프 (Undirected Graph)

• 간선을 통해서 양방향으로 갈 수 있다
• (A, B), (B, A)는 동일한 간선

 

▶ 방향 그래프 (Directed Graph)

• 일방통행처럼 간선을 통해서 단방향으로만 갈 수 있다
• (A, B), (B, A)는 서로 다른 간선

 

▶ 가중치 그래프 (Weighted Graph) / 네트워크 (Network)

• 간선에 비용/가중치가 할당된 그래프

 

 

그래프 용어

▶ 부분 그래프 (Subgraph)

- 어떤 그래프의 정점, 간선들의 일부로 이루어진 그래프

• ex) G2는 G1의 부분 그래프

 

▶ 정점의 차수 (degree)

- 한 정점으로부터 간선으로 연결된 다른 정점들의 개수

• ex1) 정점 1의 차수 = 2
• ex2) 정점 2의 차수 = 4

 

▶ 연결 그래프 (Connected Graph)

• 그래프 G에 대해서 모든 정점쌍에 대하여 항상 경로가 존재하는 무방향 그래프 

 

▶ 완전 그래프 (Complete Graph)

• 그래프 G에 대해서 정점이 n개 이면, 간선의 수 = n*(n-1)/2개