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

그래프

                 

                    <An Undirected Graph>                                          <Directed Graph>

• 인접(Adjacency)

(U,V)라는 간선이 있으면, 정점 V와 정점 U가 인접하다 라고 합니다.

하지만 여기에서 방향성과 무방향성의 표현이 다릅니다.

방향성 그래프

정점 B는 정점 A에 인접한다. 하지만 정점 A는 정점 B에 인접하지 않는다.

도착하는 정점에 맞춰서 이야기합니다.

인접관계가 동일하지 않습니다.

무방향성 그래프

정점 B는 정점 A에 인접한다. 그리고 정점 A도 정점 B에 인접한다.

인점관계가 동일합니다.

• 차수(Degree)

한 정점에 관하여 다른 정점이 얼마나 연결이 되어있는지를 표현하는 것입니다.

방향성 그래프

방향이 있기 때문에 진출차수와 진입차수로 나눌 수 있습니다.

정점 B의 진출 차수는 2이다.

정점 B의 진입 차수는 1이다.

무방향성 그래프

이 그래프는 진입/ 진출차수로 정의할 수 없기 때문에 그냥 차수만 정의 합니다.

정점 B의 차수는 3이다.

<그래프 #3>

• 경로(Path)

정점(V)로 부터 정점(U)까지 가는데 들려야하는 정점의 순서를 경로라고 합니다.

경로의 길이는 경로 사이에 있는 간선의 수입니다

<A,B,C,D> 는 경로이다. 그리고 경로의 길이는 3입니다.

<A,C,D> 는 경로이다. 그리고 경로의 길이는 2입니다.

단순 경로(Simple path)

경로에 있는 모든 정점이 서로 다른 경우입니다.

단순 경로가 필요한 이유는 출발점에서 도착점까지 경로를 구할 때 이미 방문한 곳을 또 가는 경우가 발생할 수 있습니다. 이렇게 되면 효율적이지 못합니다. 그래서 단순 경로가 필요합니다.

<A, B, C, D>는 단순 경로

<A, B, B, C, D> 는 단순 경로가 아닙니다.

• 순환과 단일순환(Cycle and Simple Cycle)

어떠한 경로에서 출발점과 도착점이 같으면 순환이라고 한다.

그래프 #3

<A, B, C, A>는 단일 순환입니다.

<A, B, C, D, C, A>는 순환이지만 단일 순환은 아닙니다.

비순환 그래프(An acyclic graph)

순환이 없는 그래프입니다.

연결 그래프(A connected graph)

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

연결 요소(Connected components)

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