14-1. 그래프의 이해와 종류

그래프의 역사와 이야깃거리

“모든 다리를 한 번씩만 건너서 처음 출발했던 장소로 돌아올 수 있는가?”

불가능하다. 정점 별로 연결된 간선의 수가 모두 짝수여야, 간선을 한 번씩만 지나서 처음 출발했던 정점으로 돌아올 수 있다

간선 : 다리정점 : 다리가 연결하는, 강으로 구분이 되는 땅

그래프의 이해와 종류

정점(vertex) : 연결의 대상이 되는 개체 또는 위치간선(edge) : 정점들 사이의 연결정점과 간선을 이용해 표현한 자료구조가 그래프

1. 무방향 그래프(undirected graph): 연결 관계에 있어서 방향성이 없는 그래프

   

2. 방향 그래프(directed graph) 혹은 다이그래프(digraph): 간선에 방향정보가 포함된 그래프

   

3. 완전 그래프: 각각의 정점에서 다른 모든 정점을 연결한 그래프방향 그래프의 정점의 수 = 무방향 그래프 정점의 수 x 2

   

가중치 그래프(Weigh Graph)와 부분 그래프(Sub Graph)

1. 가중치 그래프: 간선에 가중치 정보를 두어서 구성한 그래프

   

2. 부분 그래프: 원 그래프의 일부 정점 및 간선으로 이뤄진 그래프

   

그래프의 집합 표현

1. 무방향 그래프

   

• 그래프 G의 정점 집합 : V(G)
• 그래프 G의 간선 집합 : E(G)
• V(G1) = {A, B, C, D} E(G1) = {(A, B), (A, C), (A, D), (B, C), (C, D)}