12강. 그래프의 기초

[ 목차 ]

1. 그래프 G

2. 방향성 그래프

3. 무방향성 그래프

4. 인접

5. 차수

6. 경로

7. 순환과 단일순환

8. 그래프

9. 강한 연결과 강한 연결 요소

10. 무방향성 그래프와 방향성 그래프의 변환

11. 완전 그래프

12. Dag

13. 트리

14. 간선의 개수

 

1. 그래프 G

1) 그래프 G는 (V, E)의 쌍

2) V는 정점의 집합이고 E는 간선의 집합

3) 정점은 독립된 개체로 동그라미로 표현

4) 간선은 두 정점을 잇는 개체로 선이나 화살표가 있는 선으로 표현

 

2. 방향성 그래프

1) 방향성을 있는 간선을 가지고 있는 그래프

2) 간선이 방향을 가지기 때문에 화살표가 잇는 선을 사용

3) 각 간선은 한 정점을 떠나서 한 정점으로 들어감

4) 일반적으로 각 정점은 숫자나 이름으로 구분

   V = {1, 2, 3, 4, 5, 6}

5) 각 간선은 간선이 떠나고 도착하는 정점의 쌍을 순서대로 적은 것으로 구분

    E = {(1,2), (2,2), (2,4), (2.5) ,(4,1), (4,5), (5,4), (6,3)}

6) 방향성 그래프에서 두 개의 정점에 대해 최대 2개의 간선이 존재

 

3. 무방향성 그래프

1) 무방향성 간선을 가진 그래프

2) 방향이 없으므로 직선을 사용

3) 간선 (u,v)와 간선 (v,u)는 같음

 

4. 인접

1) (u,v)라는 간선이 있다면 정점v와 정점 u가 인접한 것

2) 무방향성 그래프에서는 인접관계가 동일 : 정점 u가 정점 v에 인접 하다면 정점 v도 정점 u에 인접

3) 방향성 그래프에서는 같지 않음 : 정점 2는 정점 1에 인접하지만 정점 1은 정점 2에 인접하지 않음

 

5. 차수

1) 정점의 진출차수(out-degree) : 정점을 나가는 간선의 수

2) 정점의 진입차수(in-degree) : 정점으로 들어오는 간선의 수

3) 차수 = 진출차수 + 진입차수

4) 무방향성 그래프에서 진입차수와 진출차수는 정의할 수 없으면 차수만 정의 가능

5) 특정 정점의 차수가 높다는 것은 해당 정점이 중심역할을 한다는 의미를 가짐

 

6. 경로

1) 정점 u로부터 정점 v까지의 정점의 순서를 의미

2) 정점의 순서가 <v0, v1, v2, ..., vk)라고 할 떄 v0 = u, vk = v이고 각 vi+1가 vi에 인접한 경우

3) 경로의 길이는 경로에 있는 간선의 수를 의미

4) 단순경로 : 경로에 있는 모든 정점들이 서로 다른 경우를 의미

 

7. 순환과 단일순환

1) 순환(cycle) : 경로에서 출발점과 끝점이 같은 것

2) 단일순화 : 경로에서 한번 방문한 정점을 다시 방문하지 않은 경우

 

8. 그래프

1) 비순환 그래프 : 순환이 없는 그래프

2) 연결 그래프 : 정점의 모든 쌍이 경로를 가지는 무방향성 그래프

3) 연결 요소 : 무방향성 그래프에서 정점들이 최대한 연결되어 있는 하위 그래프

 

9. 강한 연결과 강한 연결 요소

1) 강한 연결 : 방향성 그래프에서 정점의 각 쌍이 서로 도달 가능하다면 강하게 연결되어 있다고 지칭

2) 강한 연결 요소 : 방향성 그래프에서 최대한 많은 정점을 강하게 연결한 하위 그래프

 

10. 무방향성 그래프와 방향성 그래프의 변환

1) 무방향성->방향성 :  간선(u,v)을 (u,v)와 (v,u)의 두 개의 간선으로 변환

2) 방향성 -> 무방향성 : 간선(u,v)을 무방향성 그래프(u,v)로 변환

3) 1)을 다시 무방향성으로, 2)를 다시 방향성으로 바꿀 시 원래대로 변화하는가? 1)의 경우에만 해당

 

11. 완전 그래프

1) 무방향성 그래프에서 모든 정점의 쌍이 서로 인접하는 경우

2) 정점의 개수가 n개라면 간선의 수는 

3) 포레스트 : 순환하지 않는 무방향성 그래프

4) 트리 : 포레스트가 연결되어 있는 경우로, 연결된 비순환 무방향성 그래프라고도 지칭

 

12. Dag

1) 비순환 방향성 그래프

 

13. 트리

1) 연결된 비순환 무향성 그래프

2) 어떤 두 정점들도 단일 단순 경로로 연결

3) 간선을 제거한다면 그래프는 더이상 연결되지 않음

4) 간선 하나를 추가한다면 그래프는 순환을 포함

5) (E = V -1)을 만족

 

14. 간선의 개수

1) 방향성 그래프 : E <= V제곱

2) 비방향성 그래프 : E <= V(V-1)/2