๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

DAG1

14-4๊ฐ•. DAG์™€ ์œ„์ƒ์ˆœ์„œ DAG (Directed Acyclic Graph) : ๋ฐฉํ–ฅ ์‚ฌ์ดํด(directed cycle)์ด ์—†๋Š” ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„. (์ž๊ธฐ ์ž์‹ ์œผ๋กœ ๋Œ์•„์˜ค์ง€ ์•Š๋Š” ๋ฐฉํ–ฅ๊ทธ๋ž˜ํ”„..) ์˜ˆ) ์ž‘์—…๋“ค์˜ ์šฐ์„ ์ˆœ์œ„ ์œ„์˜ ๊ทธ๋ž˜ํ”„์—์„œ b๊ฐ€ ๋˜๊ธฐ ์œ„ํ•ด์„œ๋Š” a๊ฐ€ ๋ฐ˜๋“œ์‹œ ์„ ํ–‰๋˜์–ด์•ผ ํ•œ๋‹ค! ์œ„์ƒ์ •๋ ฌ (topological ordering) - DAG์—์„œ ๋…ธ๋“œ๋“ค์˜ ์ˆœ์„œํ™”(sorting) .. v1, v2, ..., vn. ๋‹จ ๋ชจ๋“  ์—์ง€(vi, vj)์— ๋Œ€ํ•ด์„œ i < j๊ฐ€ ๋˜๋„๋ก! ์œ„์˜ ๊ทธ๋ž˜ํ”„์—์„œ ์œ„์ƒ์ •๋ ฌ์„ ํ–ˆ์„ ๋•Œ, ์™ผ์ชฝ์—์„œ ์˜ค๋ฅธ์ชฝ ๋ฐฉํ–ฅ์œผ๋กœ ์ •๋ ฌํ–ˆ์„ ๋•Œ, a-g-... ๋˜๋Š” a-b-... ์ธ๋ฐ, ์—ญ๋ฐฉํ–ฅ์œผ๋กœ ๊ฐ€๋ฉด ์•ˆ ๋œ๋‹ค. (์˜ค๋ฅธ์ชฝ์—์„œ ์™ผ์ชฝ์œผ๋กœ ๊ฐ€๋ฉด ์ ˆ๋Œ€ ์•ˆ ๋œ๋‹ค.) ์–ด๋–ค ๋…ธ๋“œ์— ๋Œ€ํ•ด์„œ ๋“ค์–ด์˜ค๋Š” ๋…ธ๋“œ์˜ ๊ฐฏ์ˆ˜๋ฅผ in-degree, ๋‚˜๊ฐ€๋Š” ๋…ธ๋“œ์˜ .. 2020. 12. 8.

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”