## 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 sortortopological orderingofa directed graphis 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 ์ ๊ทธ๋ํ ๊ตฌ์กฐ๊ฐ ์ด๋ค๊ฑด์ง ๊ถ๊ธํด์ ์ฐพ์๋ดค์ต๋๋ค ๐