공부/알고리즘2011. 7. 13. 11:54


Graph basics

그래프는 vertex(node) set과 edge(link) set으로 구성되어 있다.

directed graph
directed graph는 방향이 있는 edge를 사용하는 그래프.
한 vertex가 어떤 edge의 끝점일 때 그 edge는 그 vertex와 incident하다고 한다. 
self-loops - 자기자신한테로 가는 edge.
edge는 vertex의 순서쌍으로 표시할 수 있다. (예 : E= {(1,2), (2,2)}, 숫자는 vertex)

undirected graph
방향이 없는 edge 사용
방향이 없으니까 Edge (u,v) 는 edge (v,u)하고 같다.
self-loops가 없다.
Adjacency - 두 vertex 사이에 edge가 있을 때 둘이 adjacent 하다고 한다.

Degree
out-degree 자기로부터 나가는 edge의 수
in-degree 자기로 들어오는 edge의 수.
한 노드의 degree는 out-degree + in-degree
undirected graph에서는 in, out degree가 없다. 그냥 한 vertex에 incident한 edge의 수를 degree라 한다.

Path
한 vertex서 다른 vertex까지 가는 길. edge를 지나는 vertex들의 집합으로 볼 수 있다.
path의 length는 path안에 있는 edge의 수.
한 vertex에서 다른 vertex까지의 path가 있을 때 두 vertex는 reachable하다라고 한다.

Simple path
같은 vertex를 두번 이상 지나지 않는 path.

Cycle
path의 시작 vertex와 끝 vertex가 같을 때.
사이클이 없으면 acyclic graph

Connected graph
undirected 그래프에서 임의로 2개 vertex를 선택하였을 때 path가 존재.

connected components
undirected connected graph을 모아논 graph

Strongly connected
directed graph에서 임의 두 vertex의 path가 있을 때

Strongly connected components
directed connected graph들을 모아논 graph

Complete graph
undirect graph의 임의 두 vertex가 adjacent할 때
edge 개수 : n(n-1)/2

Bipartite graph
undirected 그래프를 두개의 파티션을 나누는데, 각각의 파티션안에는 edge가 없고 서로의 파티션간에 edge가 있는 그래프. 

Forest
tree들의 모음
사이클이 없고, undirected graph

Tree
사이클 없고, connected한 undirected graph
사이클이 없으니까 두 vertex는 simple path가 하나밖에 없다.
edge 하나가 제거되면 graph는 disconnected가 된다.
edge 하나가 추가되면 graph는 사이클이 생긴다.
|E| = |V|-1

Dag
Directed Acyclic Graph

Handshaking lemma
모든 vertex들의 degree 합은 2*(edge 수). 왜냐하면 edge 하나가 vertex 2개의 degree를 만들기 때문.

Edge의 수
undirected graph
최대 |V|(|V|-1)/2. (완전그래프가 될 때)

directed graph
위에거에 곱하기 2에다가 self loop edge를 가질 수 있으므로 더하기 |V|. 계산하면 |V|^2이고 이는 최대로 가질 수 있는 edge 갯수이다.

그래프 구현방법

1. 행렬
vertex u, v에 edge가 있으면 행렬 M(u,v)의 값이 1, 없으면 0.
Θ(V^2) space, undirected graph이면 행렬이 main diagonal을 기준으로 symmetry하므로 Lower matrix만으로 충분.
2. 리스트
vertex별로 리스트 하나씩. adjacent한 vertex가 리스트의 노드가 된다.
Θ(V+E) space

그래프가 sparse 하면 행렬에 빈공간이 많으므로 리스트가 효율적, dense하면 행렬이 edge하나를 bit만으로 표현할 수 있으니 더 효율적.
모든 edge를 방문하고자 할 때 행렬은 존재하지 않는 edge도 방문한다. 리스트는 있는 edge만 방문한다.

edge에 값이 있는 weighted graph일 때는 행렬에 1대신에 weight값을 넣고, 리스트로 구현할 때는 각 노드에 weight 항목을 추가한다.

Transpose

main diagonal을 기준으로 대칭했을 때, 두 행렬이 같으면 transpose. 그래프로 봤을 땐 edge의 방향을 바꾸는 것. undirected graph는 바꿔도 변함이 없으므로 transpose이다.

Breadth-first-search

시작 vertex에서 거리가 가까운 노드부터 탐색.
탐색한 edge와 vetex들은 tree를 이룬다.
vertex들을 큐에 넣어 거리가 가까운 노드부터 탐색한다.
탐색여부는 색깔로 구분할 수 있다. 탐색안된것, 탐색중, 탐색완료.
모든 vertex는 최대 한번 탐색된다.
모든 edge는 최대 두번 탐색된다. 인접 vertex 찾아서 enqueue할 때, dequeue해서 인접vertex 찾을 때. 
수행시간 O(V+E), reachable 하지 않은 것이 있어서 Θ가 아님.

Depth-first-search

이것도 vetex에 색깔을 넣어 탐색여부를 알 수 있다. white는 탐색안한 vertex, gray는 탐색중인 vertex, black은 그 vertex의 모든 인접 vertex를 다 조사하고 끝난 vertex.

Parenthesis theorem
한 노드가 gray인 기간. 노드가 탐색이 시작되고 끝날 때까지의 기간.
자식이 끝나야 부모가 끝나기 때문에 시간간격이 부모가 자식을 포함하고, 겹쳐 지는 경우는 없다.

edge의 분류
tree edges
depth-first-forest(depth-first-search를 하면 트리들의 집합이 만들어진다)의 edge들
(u,v) edge에서 v가 white인 edge. 

back edges
depth first tree에서 자식에서 조상으로 가는 edge, self loop도 back edge.
(u,v) edge에서 v가 grey인 edge

Forward edges
조상에서 후손으로 가는 edge
(u,v) edge에서 v가 black인 edge (cross edge일수도 있다. u,v가 포함관계가 아닐 경우.)

cross edges 
다른 depth first tree에서 온 edge
 
undirected graph일 때, depth-first search하면 모든 edge는 tree edge이거나 back edge이다.
forward edge는 back edge가 되고(자식 노드에서 먼저 edge를 탐색하기 때문에)
cross edge는 tree edge가 된다. (unconnected 였는데 connected가 되기 때문)

running time : Θ(V+E), list로 구현했을 때.

스택을 사용한다.

Topological sort

그래프가 DAG(엣지방향이 있고 사이클이 없는 그래프)일 때, 모든 엣지를 왼쪽에서 오른쪽 방향으로 되도록 vertex를 일렬로 배열 할 수 있다.

출처 : homepages.ius.edu

 사이클이 있으면 불가능. no back edge. right에서 left로 가는 edge가 있기 때문이다.

 in-degree가 0인 vertex를 왼쪽부터, out-degree가 0인 것을 오른쪽부터 둔다.
Depth first search를 돌려서 finish time이 빠른 vertex부터 맨 오른쪽부터 놓는다.

 

'공부 > 알고리즘' 카테고리의 다른 글

Single-Source Shortest Paths  (0) 2011.07.13
Minimum spanning tree (최소신장트리)  (0) 2011.07.13
Data Structures for Disjoint Sets  (0) 2011.07.11
Greedy Algorithms  (0) 2011.07.11
Dynamic Programming  (0) 2011.07.09


Posted by skyjumps