## Q. DAG가 뭔가요?

A : DAG는 다들 아시다시피 directed acyclic graph 입니다.

## Q. 그래서 directed acyclic graph 가 뭔가요?

A : directed graphdirected cycles를 가지지 않았으면 DAG 입니다.

## Q. 그러면 directed graph와 directed cycles가 뭔가요?

먼저 directed graph 의 정의부터 보면…

Def. In formal terms, a directed graph is an ordered pair G = (V, A) where

• V is a set whose elements are called vertices, nodes, or points;
• A is a set of ordered pairs of vertices, called arrows, directed edges (sometimes simply edges > with the corresponding set named E instead of A), directed arcs, or directed lines.

아, 영어라 머리가 아파요… 한글로 보시죠..

유향 그래프는 $$\Gamma =(V,E)$$는 집합 $$V$$와, $$V$$의 순서쌍들로 구성된 집합 $$E\subset V\times V$$의 순서쌍이다.

이 경우, $$e=(u,v)$$라면 $$e$$를 $$u$$에서 $$v$$로 가는 변이라고 하며, 꼭짓점 $$v$$는 변 $$e$$의 머리, 꼭짓점 $$u$$는 변 $$e$$의 꼬리라고 한다.

쉽게 얘기해서 방향이 있는 그래프네요.

그럼 directed cycles는 뭘까요?

A directed cycle graph is a directed version of a cycle graph, with all the edges being oriented in the same direction.

아, 방향이 있는 순환 그래프이네요! 모든 edge가 같은 방향을 가지고 있는거네요!

Def. A directed cycle in a directed graph $$G$$ is a path $$v_1, v_2, …, v_k$$ in $$G$$ in which $$v_1 = v_k, k > 2$$, and the first $$k-1$$ nodes are all distinct.

라고도 다른데서 정의하는 걸로 봐서는 같은 걸 의미하네요!

## 정리해봅시다.

DAG는 directed graphdirected cycles를 가지지 않은 것이며,

방향이 있는 그래프에서 방향이 있는 순환 그래프를 포함하지 않으면 되는 거네요!

Def. A DAG is a directed graph that contains no directed cycles

(Example of a directed acyclic graph, https://en.wikipedia.org/wiki/Directed_acyclic_graph)

어쩐지 이름부터가 Directed Acyclic Graph(유향 비순환 그래프) 였네요.

## Q. 이거 어디서 본 것 같아요!

A. 아, 위상 정렬(Topological Sorting)을 아시는군요!

### 네? 모르는데요…

모르시면, 정의부터 봐야겠네요 ㅎㅎ

그럼 위상 정렬(Topological Sorting)의 정의는 뭘까요?

그래프 이론 책이 없어서 위키피디아를 또 찾아가보겠습니다.

In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

Def. A topological ordering of a directed graph $$G = (V, E)$$ is an ordering of its nodes as $$v_1, v_2, …, v_n$$ so that for every edge $$(v_i, v_j)$$ we have $$i < j$$.

오 명확해졌습니다!

Directed graph의 topological ordering 이란,

모든 vertices의 선형 정렬인데, 모든 directed edge (u, v) 들에 대해서, u는 무조건 v 전에 선행한다는 거네요!

즉, 다시 말하면

처럼 선형으로 표현가능하지만, 같은 그래프를

처럼 정렬하면 안된다는 겁니다.

왜냐하면, D → E edge가 있지만, E가 D보다 선행되었기 때문이죠.

### 그런데 앞에 소개한 둘이 사실 같은게 아닌가요?

네, 같아 “보입니다.”

그런데 진짜 같은 걸까요?

정확히 어떤게 같다고 표현해야할까요?

### 명제를 만들어봅시다.

우선 앞에서 정의한 두 친구를 데려와 봅시다.

DAG 란, directed graphdirected cycles를 가지지 않은 것입니다.

Topological Sorting이란, directed graph들의 vertexs를 edge의 방향에 거스르지 않고 나열한 것입니다.

두 친구 모두 directed graph 에 대해서 얘기를 하고 있네요.

그럼 증명할 명제를 만들어보면…

For a directed graph G, G is a DAG if and only if G has a topological order

가 됩니다!

그러면 이제 위의 명제를 증명하면 됩니다.

### 명제를 증명해봅시다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Lemma. For a directed graph G, if G has a topological order, then G is a DAG. Pf. (by contraction) Suppose that G has a topological order. Suppose that G has a directed cycle C. Let vi be the lowest-indexed vertex in C and let vj be the vertex just before vi in C. thus, (vj, vi) is an edge. WLOG, we have i < j. On the other hand, Since (vj, vi) is an edge and v1,... ,vn is a topological order, we must have j < i. (-><-) So, G has a no directed cycle. Therefore, G is a DAG. 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Lemma. For a directed graph G, if G is a DAG, then G has a topological order. Pf. (by induction on i) (i = 1) true, because topological ordering is G. (i = n + 1) Suppose that if G is a DAG of size <= n, G has a topological order. Given DAG G with n+1 vertexs. Let v be a vertex with no incoming edges. G - {v} is a DAG, since deleting v cannot create cycles. By hypothesis, G - {v} has a topological order. Create topological ordering for G: - Place v first; then append topological ordering of G - {v} - This is valid since v has no incoming edges. By induction, the lemma is proven. 

## 많이 본 모양인데 말이죠… 어디서 봤을까요?

• Genealogy and version history
• Git branch 의 구조가 DAG네요.

• Scheduling

• Data processing networks
• Data compression

## 그런데 왜 이걸 했을까요? 🤔

Git branch 의 그래프 구조가 어떤건지 궁금해서 찾아봤습니다 🙂