[기초 알고리즘] 그래프(기초Ⅲ)

그래프

• 강한 연결과 강한 연결 요소
  

강한 연결(Strongly connected)

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

무방향성 그래프에서는 방향에 관계 없기 때문에 방향성 그래프에서는 이렇게 표현한다.

강한 연결 요소

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

• 완전 그래프(A complete graph)

무방향 그래프에서 모든 정점의 쌍이 서로 인접한 경우

Q) 정점이 n 개라면 간선은 몇개 일까?

                                             <graph #1>                                  <graph #2>                               <graph #3>

A) #1은 1개  / #2는 3개  / #3는 6개

• 포레스트(Forest)

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

어떤 정점 두 곳을 정해 경로를 만들었을 때 시작점과 도착점이 같지 않는 것을 말합니다.   

• 트리(Tree)

포레스트가 연결되어 있는경우

즉, 연결된 비순환 무방향성 그래프

위에 말을 풀어서 쓰면 트리를 만족하기 위한 조건이 됩니다.

연결이 되어 있어야 한다 / 비순환이여야한다. / 무방향성 그래프여야한다.

이 두가지를 밑에 예를 보고 이해를 하면 쉽게 이해가 될겁니다.

                    

   <Q. 1>                                        <Q. 2>                                         <Q. 3>

일단 Q 1은 트리도 아니고 포레스트도 아닙니다.

 그 이유는 포레스트와 트리 모두 순환하지 않아야 하는데 순환이기 떄문입니다.

 Q 2는 트리는 만족하지 못하지만 포레스트는 만족합니다.

 그 이유는 연결되어 있어야 하지만 중간에 끊겨 있기 때문에 트리는 만족하지 못한다.

 Q 3은 포레스트와 트리 모두 만족합니다.

 그 이유는 트리의 조건과 포레스트의 조건 모두 충족하기 때문입니다.