κ·Έλν
-
μ΄μ° μν κ·Έλνμ νμ©
κ·Έλνμ νμ© λ€νΈμν¬μ λ°μ΄ν° νλ¦μ΄λ μ€μΌμ€λ§, λ Όλ¦¬νλ‘ μ€κ³, μ λ ¬, νμ, μΈκ³΅μ§λ₯μ μ§μ μ 보 μμ± κ³Όμ λ± κ·Έλ¦¬κ³ μ€μνμμ λ§μ΄ μ ν μ μλ λλ‘λ§ μ€κ³λ λ²μ€ λ° μ§νμ² λ Έμ μ€κ³ λ±κ³Ό κ°μ΄ μ΄λ€ λ¬Έμ λ₯Ό ν΄κ²°νκΈ° μν λͺ¨λΈλ§ κ³Όμ μμ κ·Έλν μ΄λ‘ μ λ§€μ° μ€μνκ² μ°μΈλ€. μ΄λ¬ν λͺ¨λΈλ§μμ μ΅λ¨ κ²½λ‘λ₯Ό ꡬνκ±°λ μ 보 νμμ νλ λ°©λ²μ΄ λ§μ΄ μ°μΈλ€. μ΅λ¨ κ²½λ‘ λ¬Έμ (Shortest Path Problem) |E|>0 μΈ μ°κ²° κ·Έλν G=(V,E) μμ μ μ v1,v2βV κ°μ κ°μ₯ μ§§μ 거리μ κ²½λ‘λ₯Ό μ°Ύλ λ¬Έμ μ§λμ μ΄λ€ μ§μ Aμμ λ€λ₯Έ μ§μ Bλ‘ μ΄λνλ κ²½λ‘λ, λ€νΈμν¬μ μ΄λ€ νΈμ€νΈ Aμμ λ€λ₯Έ νΈμ€νΈ Bλ‘ μ΄λνλ κ²½λ‘λ λ€μν μ μ..
0 2022.11.27 -
μ΄μ° μν μ€μΌλ¬μ ν΄λ°ν΄
μ€μΌλ¬μ ν΄λ°ν΄ μ°κ²° κ·Έλνμλ νλμ μ μ μμ λ€λ₯Έ μ μ μΌλ‘ κ°λ λ€μν κΈΈμ΄ μ‘΄μ¬ν μ μλλ°, κ·Έ μ€μμ κ°μ λ³μ λ°λ³΅μ μΌλ‘ μ§λμ§ μλ κΈΈμ΄ κ²½λ‘μ΄λ€. μν(Cycle) / νλ‘(Circuit) μ°κ²° κ·Έλνμμ μμνλ μ μ κ³Ό λλλ μ μ μ΄ κ°μ κ²½λ‘ κΈΈμ΄(Length) κ²½λ‘ λλ μνμ ꡬμ±νλ λ³μ μ ν κ·Έλνμ ν¬ν¨λλ μμμ μ μ μμ λ€λ₯Έ μ μ νΉμ λ€μ μλμ μ μ μΌλ‘ κ°λ κΈΈμ λ€μνλ€. κ·Έμ€ λ³μ ν λ²μ©λ§ μ§λ λ€λ₯Έ μ μ μΌλ‘ κ°λ κΈΈμ κ²½λ‘μ΄κ³ , μλμ μ μ μΌλ‘ λ€μ λμμ€λ κ²½λ‘λ μνμ΄λ€. μ (1) aβcβdβf (2) aβeβcβdβbβf (3) aβcβeβa (4) aβeβcβa (5) $a - c - d ..
0 2022.11.26 -
μ΄μ° μν κ·Έλνμ νν
κ·Έλνμ νν κ·Έλνλ μνμ κΈ°νΈμ κ·Έλ¦ΌλΏ λ§ μλλΌ κ·Έλνλ₯Ό μ΄μ©ν μ°μ°μ΄λ λ°μ΄ν°μ ꡬ쑰λ₯Ό λνλ΄κΈ° μν΄ νλ ¬μ΄λ 리μ€νΈ ννλ‘ νννκΈ°λ νλ€. μΈμ νλ ¬(Adjacency Matrix : AG) κ·Έλν G=(E,A) μμ |V|=n μΌ λ, nΓn νλ ¬ AG=[aij] aij={ν΄λΉ μ μ μ κ·Όμ νλ λ³μ μ,(vi,vj)βE0,(vi,vj)βE κ΄κ³λ₯Ό νλ ¬λ‘ νννλ κ΄κ³ νλ ¬μ κ΄κ³ μ§ν©μ μμμ μμκ° μλμ§ μλμ§λ₯Ό 1κ³Ό 0μΌλ‘ νννλ νλ ¬λ‘, λΆμΈ νλ ¬μ ννμ΄λ€. κ·Έλνλ ..
0 2022.11.26 -
μ΄μ° μν κ·Έλνμ μ’ λ₯
κ·Έλνμ μ’ λ₯ κ·Έλνλ μ μ κ³Ό λ³μ΄ μ΄λ»κ² ꡬμ±λλμ§μ λ°λΌ μ’ λ₯λ₯Ό ꡬλΆνλ€. λΆλΆ κ·Έλνμ μ μ₯ λΆλΆ κ·Έλν λΆλΆ κ·Έλν(Subgraph) κ·Έλν G=(V,E) μ λνμ¬, Vβ²βV μ΄κ³ Eβ²βE μΈ μ μ κ³Ό λ³μΌλ‘ ꡬμ±λ Gβ Gβ² μΈ κ·Έλν Gβ²=(Vβ²,Eβ²) μ μ₯ λΆλΆ κ·Έλν(Spanning Subgraph) κ·Έλν G=(V,E) μ λνμ¬, Vβ²=V μ΄κ³ Eβ²βE μΈ μ μ κ³Ό λ³μΌλ‘ ꡬμ±λ κ·Έλν Gβ²=(Vβ²,Eβ²) λΆλΆ κ·Έλν Gβ² μ μ΄λ€ κ·Έλν G μ ν¬ν¨λ μ μ κ³Ό λ³μ μΌλΆ λλ μ μ²΄λ‘ κ΅¬μ±λ κ·Έλνμ΄λ€. λΆλΆ κ·Έλν Gβ² μ ꡬμ±νλ μ μ μ μ§ν©κ³Ό λ³μ μ§ν©μ κ°κ° κ·Έλν G μ μ ..
0 2022.11.25 -
μ΄μ° μν κ·Έλνμ κ°λ
κ·Έλνμ κ°λ μ κ³Ό μ μ μ΄μ©ν΄ κ°λ , ꡬ쑰 λλ κ³Όμ λ±μ μ΄ν΄νλ λ° νμν μ£Όμ μμ κ°μ κ΄κ³, 거리, λΉμ© λ±μ μκ°μ μΌλ‘ ννν λꡬλ₯Ό κ·Έλν(Graph)λΌκ³ νλ€. κ·Έλνλ κΈμ΄λ μμμΌλ‘λ 볡μ‘νκ³ μ΄λ ΅κ² ννλλ κ²μ κ·Έλ¦ΌμΌλ‘ νννκΈ° λλ¬Έμ μ»΄ν¨ν° μμ€ν μ νλ‘λ λ€νΈμν¬ μ€κ³λ ꡬ쑰, νλ‘κ·Έλ¨μ μκ³ λ¦¬μ¦, μΈκ³΅μ§λ₯μ μ§μ μ 보μ νμ κ³Όμ λ° λ΄μ© λ±μ νννλ λ° ν¨μ¨μ μ΄κ³ ν¨κ³Όμ μΌλ‘ νμ©λλ€. κ·Έλνλ μ μ κ³Ό λ³μΌλ‘ ννλκΈ° λλ¬Έμ μ μ μ λν μ 보μ λ³μ λν μ 보λ₯Ό μ μν¨μΌλ‘μ¨ κ·Έλνλ₯Ό μ μνκ³ νννλ€. κ·Έλνλ λ³΄ν΅ κ·Έλ¦Ό ννλ‘ νννμ§λ§, μ§ν© ννκ³Ό κ°μ μνμ κΈ°νΈλ‘ ννν μλ μλ€. κ·Έλνμ μ μμ νν κ·Έλν(Graph : G=(V,E) ) 곡μ§ν©μ΄..
0 2022.11.25