Home DAG๊ฐ€ ๋ญ”๊ฐ€์š”? ๐Ÿค”
Post
Cancel
Preview Image

DAG๊ฐ€ ๋ญ”๊ฐ€์š”? ๐Ÿค”

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

800px-Tred-G.png

(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 ์ „์— ์„ ํ–‰ํ•œ๋‹ค๋Š” ๊ฑฐ๋„ค์š”!

์ฆ‰, ๋‹ค์‹œ ๋งํ•˜๋ฉด

correct-topological-sorting.png

์ฒ˜๋Ÿผ ์„ ํ˜•์œผ๋กœ ํ‘œํ˜„๊ฐ€๋Šฅํ•˜์ง€๋งŒ, ๊ฐ™์€ ๊ทธ๋ž˜ํ”„๋ฅผ

incorrect-topological-sorting.png

์ฒ˜๋Ÿผ ์ •๋ ฌํ•˜๋ฉด ์•ˆ๋œ๋‹ค๋Š” ๊ฒ๋‹ˆ๋‹ค.

์™œ๋ƒํ•˜๋ฉด, 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

๊ฐ€ ๋ฉ๋‹ˆ๋‹ค!

๊ทธ๋Ÿฌ๋ฉด ์ด์ œ ์œ„์˜ ๋ช…์ œ๋ฅผ ์ฆ๋ช…ํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

๋ช…์ œ๋ฅผ ์ฆ๋ช…ํ•ด๋ด…์‹œ๋‹ค.

More_details_be_omitted.jpg

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๋„ค์š”.

git-model.png

  • Scheduling

Pert_chart_colored.svg

  • Data processing networks
  • Data compression

๊ทธ๋Ÿฐ๋ฐ ์™œ ์ด๊ฑธ ํ–ˆ์„๊นŒ์š”? ๐Ÿค”

Git branch ์˜ ๊ทธ๋ž˜ํ”„ ๊ตฌ์กฐ๊ฐ€ ์–ด๋–ค๊ฑด์ง€ ๊ถ๊ธˆํ•ด์„œ ์ฐพ์•„๋ดค์Šต๋‹ˆ๋‹ค ๐Ÿ™‚

References

This post is licensed under CC BY 4.0 by the author.

[Rust] Struct std::collections::HashMap ์ •๋ฆฌ

[Rust] Cargo ํ”„๋กœ์ ํŠธ์—์„œ Author ์ˆ˜์ •ํ•˜๊ธฐ