3. Decompositions of graphs

3.1. Why graphs?

많은 문제들이 그래프를 이용해 풀 수 있다. 그래프 채색, 그래프의 기본적 연산. 그래프는 정점들과 간선들로 이루어진다. 이 간선들은 방향일 수도 있고 비방향일 수도 있다.

3.1.1. How is a graph represented?

그래프는 인접 행렬로 나타낼 수도 있고 인접 리스트로 나타낼 수도 있다. 간선이 희박하면 인접 리스트가 낫다.

3.2. Depth-first search in undirected graphs

3.2.1. Exploring mazes

미로를 어떻게 탐색할까? 이는 재귀적으로 수행할 수 있다.

3.2.2. Depth-first search

앞에서 했던 접근법을 깊이 우선 탐색이라 한다.

procedure dfs(G)

for all v ∈ V:
    visited(v) = false

for all v ∈ V:
    if not visited(v) : explore(v)

수행 시간은 간선에 선형이다.

3.2.3. Connectivity in undirected graphs

비방향그래프의 연결성과 연결요소는 깊이 우선 탐색으로 구할 수 있다.

3.2.4. Previsit and postvisit ordering

두 노드에 대해, previsit, postvisit 구간은 서로 겹치지 않거나 하나가 다른 한 구간을 포함한다.

3.3. Depth-first search in directed graphs

3.3.1. Types of edges

방향그래프에 대해서도 깊이 우선 탐색을 적용할 수 있다. 이러면 고려해야 할 간선의 유형이 더 많아진다.

3.3.2. Directed acyclic graphs

방향 비순환그래프는 더 특수하다. 방향그래프에 순환이 없을 것은 깊이 우선 탐색이 후방 간선이 없음과 동치이다. 방향 비순환그래프에 대해서는 정점에 대한 선형 시간 정렬이 가능해진다.

3.4. Strongly connected components

3.4.1. Defining connectivity for directed graphs

방향그래프에 대해서는 두 정점에 대해 양방향 경로가 모두 있을 때 연결성을 정의할 수 있다. 모든 방향그래프는 그 강연결요소에 대한 방향비순환그래프이다.

3.4.2. An efficient algorithm

방향그래프를 강연결요소로 분해하려면 전치그래프에 깊이 우선 탐색을 돌리고 이 때 탐색이 끝난 순서대로 비방향그래프의 연결요소 알고리즘을 돌리면 된다. 이는 선형 시간이다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중