π Graph, Tree | κ·Έλν, νΈλ¦¬
π« Graph | κ·Έλν
κ·Έλν : μ μ κ³Ό κ°μ μΌλ‘ μ΄λ£¨μ΄μ§ μλ£κ΅¬μ‘°
κ° μμλ₯Ό μ μ (Vertex) λλ λ Έλ(Node : λ§λ)λΌκ³ λΆλ₯΄κ³ , κ°μ (Edge)μ λ μ μ μ μ°κ²°νλ μ μ΄λ€.
π« Tree | νΈλ¦¬
무방ν₯μ΄λ©΄μ μ¬μ΄ν΄μ΄ μλ μ°κ²° κ·Έλν (Undirected Acyclic Connected Graph)
κ° λ Έλκ° μλ‘ λΆλͺ¨-μμ κ΄κ³λ‘ μ°κ²°λλ€.
- λΆλͺ¨-μμ κ΄κ³
- λΆλͺ¨(Parent) : μμμ κ°μ§λ λ Έλ
- μμ(Child) : λΆλͺ¨λ₯Ό κ°μ§λ λ Έλ
- 루νΈ(Root : λΏλ¦¬) λ Έλ : νΈλ¦¬μ μ΅μμ λ Έλ
리ν(Leaf : μ), λ¨λ§(Terminal) λ Έλ : μμμ΄ μλ λ§λ¨ λ Έλ
μλΈνΈλ¦¬(Subtree) : νΈλ¦¬μ μΌλΆλΆ, μ΄λ€ ν μ μ μ λν΄ κ·Έ μ μ κ³Ό κ·Έ μ μ μ μμλ€λ‘ μ΄λ£¨μ΄μ§ νΈλ¦¬
- λμ΄/λ 벨(Height/Level) : 루νΈμμ ν΄λΉ λ
ΈλκΉμ§μ 거리
- λ Έλκ° 1κ°λ§ μμ λμ λμ΄λ₯Ό 1λ‘ λλλ 0μΌλ‘ λλλμ λ°λΌ λμ΄κ° λ¬λΌμ§ μ μμ
𫧠λ€λ₯Έ λ§λ‘ (μ±μ§)
- μ°κ²° κ·Έλνμ΄λ©΄μ μμμ κ°μ μ μ κ±°νλ©΄ μ°κ²° κ·Έλνκ° μλλ©΄ λλ κ·Έλν
- β μμμ λ μ μ μ°κ²°νλ simple path(μ μ μ΄ μ€λ³΅ν΄μ λμ€μ§ μλ κ²½λ‘)κ° μ μΌν κ·Έλν
- β Vκ°μ μ μ μ κ°μ§κ³ V-1κ°μ κ°μ μ κ°μ§λ μ°κ²° κ·Έλν
- μ¬μ΄ν΄μ΄ μλ μ°κ²° κ·Έλνμ΄λ©΄μ μμμ κ°μ μ μΆκ°νλ©΄ μ¬μ΄ν΄μ΄ μκΈ°λ κ·Έλν
- Vκ°μ μ μ μ κ°μ§κ³ V-1κ°μ κ°μ μ κ°μ§λ Anyclic(=μ¬μ΄ν΄μ΄ μλ) κ·Έλν
𫧠μμμ λ Έλλ₯Ό 루νΈλ‘ λ§λ€ μ μλ€
νΈλ¦¬λ₯Ό ꡬμ¬κ³Ό μ€λ‘ μ°κ²°λ λͺ¨μμ΄λΌκ³ μκ°ν λ,
μ무 ꡬμ¬μ μ‘κ³ μλ‘ μ¬λ €λ κ·Έ λͺ¨μμ μ¬μ ν νΈλ¦¬κ° λλ€.
λ¨, 루νΈκ° λ¬λΌμ§λ©΄ κ° λ Έλμ λΆλͺ¨κ° λ¬λΌμ§λ€. (λΆλͺ¨-μμ κ΄κ³κ° λ¬λΌμ§λ€.)