[컴퓨터 알고리즘 기초] 11. 그래프의 기초

1. 그래프 기초 

그래프 G 

그래프G는 (v,e)의 쌍이다.

• 이때 v는 정점(vertex)의 집합(set)이고 e는 간선(edge)의 집합이다.
• 정점은 독립된 개체(stand-alone object)로 동그라미로 표현한다.
• 간선은 두 정점을 잇는 개체로 선이나 화살표가 있는 선으로 표현한다.

 

방향성 그래프(Directed graph)

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

• 간선이 방향을 가지기 때문에 화살표가 있는 선(arrows)을 사용한다.
• 각 간선은 한 정점을 떠나서 한 정점으로 들어간다.
• 일반적으로, 각 정점은 숫자나 이름으로 구분한다.
• 각 간선은 간선이 떠나고 도착하는 정점의 쌍을 순서대로 적은 것으로 구분한다.
• 방향성 그래프에서 두 개의 정점에 대해 최대 2개의 간선이 존재한다.

 

무방향성 그래프(unDirected graph)

• 무방향성 간선을 가진 그래프이다.
• 간선이 방향이 없으므로 직선(line)을 사용한다.
• 간선(u,v)와 간선 (v,u)는 같다.

 

인접(Adjacency)

• (u,v)라는 간선이 있다면, 정점v 와 정점 u가 인접하다 라고 한다.
• 무방향성 그래프에서는 인접 관계는 동일하다.
• 방향성 그래프에서는 같지 않다.

 

차수(degree)

• 정점의 진출 차수(out-degree)는 정점을 나가는 간선의 수이다.
• 정점의 진입 차수(in-degree)는 정점으로 들어오는 간선의 수이다.
• 차수는 진입차수와 진출차수의 합이다.
  • degree = out-degree + in-degree
• 무방향성 그래프에서 진입차수와 진출차수는 정의할 수 없으며 차수만 정의할 수 있다.

 

경로(path)

• 정점 u로 부터 정점 v까지의 경로는 정점의 순서이다.
• 경로의 길이는 경로에 있는 간선의 수이다.
  • 예를 들어, 경로 1,2,4,5의 길이는 3이 된다.

 

단순 경로

단순 경로는 경로에 있는 모든 정점들이 서로 다른 경우이다.

경로 <1,2,4,5>는 단순 경로이지만 <1,2,4,1,2>는 단순 경로가 아니다.

 

순환과 단일순환

• 경로의 출발점과 끝점이 같으면 순환이라고한다.
• 또한 모든 정점이 다른 경우엔 단일 순환이다.
• 비순환 그래프
  • 순환이 없는 그래프
• 연결 그래프
  • 정점의 모든 쌍이 경로를 가지는 무방향성 그래프
• 연결요소
  • 무방향성 그래프에서 정점들이 최대한 연결되어 있는 하위 그래프

 

강한 연결과 강한 연결 요소

강한 연결(Strongly connected)

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

 

강한 연결 요소

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

 

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

무방향성 그래프의 간선 (u,v)을 방향성 그래프의 (u,v)와 (v,u)의 두개의 간선으로 바뀐다.

방향성 그래프 간선(u,v)을 무방향성 그래프(u,v,)로 바뀐다.

 

완전 그래프(A complete graph)

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

 

포레스트

• 순환하지 않는 무방향성 그래프

트리

• 포레스트가 연결되어 있는 경우
• 연결된 비순환 무방향성 그래프
• 두 정점은 단일 단순 경로로 연결이 된다.
• 간선을 제거한다면 그래프는 더 이상 연결되지 않는다.
• 간선 하나를 추가한다면 그래프는 순환을 포함하게된다.
• e(간선) = v(정점)-1을 만족한다.

 

Dag

비순환 방향성 그래프(A directed acyclic graph) -> 나중에 더 자세히 배워볼 예정

 

그래프에서 간선의 개수

방향성 그래프(direct graph)

e<=v^2

 

비방향성 그래프(undirect graph)

e<=v(v-1)/2