## Q. DAG๊ฐ ๋ญ๊ฐ์?

A : DAG๋ ๋ค๋ค ์์๋ค์ํผ directed acyclic graph ์๋๋ค.

## Q. ๊ทธ๋์ directed acyclic graph ๊ฐ ๋ญ๊ฐ์?

A : directed graph ๊ฐ directed 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 graph ๊ฐ directed 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 graph ๊ฐ directed 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 ์ ๊ทธ๋ํ ๊ตฌ์กฐ๊ฐ ์ด๋ค๊ฑด์ง ๊ถ๊ธํด์ ์ฐพ์๋ดค์ต๋๋ค ๐