[Algorithm]그래프(Graph)의 정의 - 그래프 추상 데이터 타입

1. 정의: G=(V, E) -> V: 공백이 아닌 노드(node) 또는 정점(vertex)의 유한집합

                            -> E: 상이한 두 정점을 잇는 간선(edge)의 유한집합

2. 무방향 그래프(undirected graph): 방향이 없는 그래프

3. 유방향 그래프(directed graph): 다이 그래프, 방향 그래프

   - 간선을 순서가 있는 두 정점의 쌍으로 표현되는 그래프

   - vi -> vk를 <vi, vk>로 표현(i= tail, k=head) 두개는 같지 않음

4. 단순 그래프: 두 정점 사이에 최대 하나의 간선만 존재 <-> 다중 그래프

5. 완전 그래프: 가능한 최대한 간선을 가진 그래프(정점 n, 최대 간선 수= 무방향그래프 n(n-1)/2, 방향 n(n-1))

6. 무방향 그래프의 한 간선(vi, vk):

   a. 정점 vi, vk는 서로 인접하고 있다

   b. 간선 (vi, vk)은 정점 vi, vk에 부속된다고함

   c. 아크 <vi, vk>는 정점 vi와 vk에 인접+ vi, vk에 부속한다고 한다.

7. 경로

  a. 경로의 길이: 경로를 구성하는 간선의 수

  b. 단순 경로: 모두 상이한 간선들로 구성된 경로

     - G1: 경로 (0,1,3,2)와 경로(0,1,3,1): 길이 모두 3

     - G2: 경로(0,1,2)는 단순 방향 경로지만 , (0,1,2,1)은 경로가 아님

8. 사이클(cycle)

   a. 첫번째 정점과 마지막 정점이 동일한 단순경로: 무방향 그래프의 사이클 길이 >= 3

                                                                                   방향 사이클 길이 >= 2

   b. 무방향 그래프 G1 경로 0, 1, 3, 0 사이클

   c. 방향 그래프 G2의 경로 0, 1, 0 사이클

   d. DAG(Directed Acyclic Graph): 방향 그래프에서 사이클이 없는 그래프

9. 연결 그래프

   a. 강력 연결(strongly connected): 방향 그래프에서 서로 다른 정점으 쌍에 대해 방향 경로가 모두 존재

   b. 약한 연결(weakly connected): 방향 그래프에서 서로 다른 모든 정점의 쌍에 대해 하나의 경로만 존재

   c. 강력 연결 요소(strong connected component): 강력 연결된 최대 부분 그래프(개수)