Skip to content

Latest commit

Β 

History

History
72 lines (49 loc) Β· 2.96 KB

Graph.md

File metadata and controls

72 lines (49 loc) Β· 2.96 KB

Graph

Graph(κ·Έλž˜ν”„)λž€?


κ·Έλž˜ν”„λŠ” 정점(Vertex)κ³Ό κ°„μ„ (Edge)으둜 이루어진 μžλ£Œκ΅¬μ‘°μ΄λ‹€.
μ—°κ²° λ˜μ–΄μžˆλŠ” μ›μ†Œκ°„μ˜ 관계λ₯Ό ν‘œν˜„ν•œ μžλ£Œκ΅¬μ‘°μž…λ‹ˆλ‹€.
κ·Έλž˜ν”„λ₯Ό G=(V,E)둜 μ •μ˜ν•˜λŠ”λ°, VλŠ” μ •μ μ˜ 집합, EλŠ” κ°„μ„ λ“€μ˜ 집합을 μ˜λ―Έν•©λ‹ˆλ‹€.



κ·Έλž˜ν”„μ™€ κ΄€λ ¨λœ μš©μ–΄

  • 정점 (vertex) : λ…Έλ“œ(node), 데이터가 μ €μž₯λ˜λŠ” κ·Έλž˜ν”„ κΈ°λ³Έ μ›μ†Œ

  • κ°„μ„  (edge) : 링크(link), μ •μ κ°„μ˜ 관계λ₯Ό λ‚˜νƒ€λƒ„

  • 인접 정점 (adjacent vertex) : 간선에 μ˜ν•΄ μ—°κ²°λœ 정점

  • λ‹¨μˆœ 경둜 (simple path) : λ™μΌν•œ 간선을 μ§€λ‚˜μ§€ μ•ŠλŠ” 경둜

  • 차수 degree = 무방ν–₯ κ·Έλž˜ν”„μ—μ„œ ν•œ 정점에 μΈμ ‘ν•œ μ •μ μ˜ 수

  • μ§„μΆœ 차수(out-degree) : λ°©ν–₯ κ·Έλž˜ν”„μ—μ„œ ν•œ μ •μ μ—μ„œ λ‹€λ₯Έ μ •μ μœΌλ‘œ λ‚˜κ°€λŠ” κ°„μ„ μ˜ 수

  • μ§„μž… 차수(in-degree) : λ°©ν–₯ κ·Έλž˜ν”„μ—μ„œ μ™ΈλΆ€μ—μ„œ ν•œ μ •μ μœΌλ‘œ λ“€μ–΄μ˜€λŠ” κ°„μ„ μ˜ 수

  • 경둜 길이(path length) : 경둜λ₯Ό κ΅¬μ„±ν•˜λŠ” κ°„μ„ μ˜ 수

  • 사이클 (cycle) : ν•œ μ •μ μ—μ„œ μ‹œμž‘ν•΄ ν•΄λ‹Ή μ •μ μœΌλ‘œ λλ‚˜λŠ” 경둜 ( ex : A-B-C-D-A )



κ·Έλž˜ν”„ μ’…λ₯˜

  1. 무방ν–₯ κ·Έλž˜ν”„
    무방ν–₯ κ·Έλž˜ν”„λŠ” 두 정점을 μ—°κ²°ν•˜λŠ” 간선에 λ°©ν–₯이 μ—†λŠ” κ·Έλž˜ν”„μ΄λ‹€.



  1. λ°©ν–₯ κ·Έλž˜ν”„
    λ°©ν–₯ κ·Έλž˜ν”„λŠ” 두 정점을 μ—°κ²°ν•˜λŠ” 간선에 λ°©ν–₯이 μ‘΄μž¬ν•˜λŠ” κ·Έλž˜ν”„μ΄λ‹€.
    κ°„μ„ μ˜ λ°©ν–₯으둜만 이동할 수 μžˆλ‹€.



  1. κ°€μ€‘μΉ˜ κ·Έλž˜ν”„
    κ°€μ€‘μΉ˜ κ·Έλž˜ν”„λŠ” 간선에 κ°€μ€‘μΉ˜(λΉ„μš©)κ°€ ν• λ‹Ήλœ κ·Έλž˜ν”„λ‘œ, 두 정점을 이동할 λ•Œ λΉ„μš©μ΄ λ“œλŠ” κ·Έλž˜ν”„μ΄λ‹€.



  1. μ™„μ „ κ·Έλž˜ν”„
    κ·Έλž˜ν”„μ˜ λͺ¨λ“  정점이 μ„œλ‘œ μ—°κ²°λ˜μ–΄ μžˆλŠ” κ·Έλž˜ν”„μ΄λ‹€. (인접 μ—°κ²°)



  1. μˆœν™˜ κ·Έλž˜ν”„
    λ‹¨μˆœ κ²½λ‘œμ—μ„œ μ‹œμž‘ 정점과 도착 정점이 λ™μΌν•œ κ·Έλž˜ν”„μ΄λ‹€. (Aμ—μ„œ μ‹œμž‘-> Aμ—μ„œ 끝 κ°€λŠ₯)

  1. λΉ„μˆœν™˜ κ·Έλž˜ν”„
    사이클 κ·Έλž˜ν”„λ₯Ό μ œμ™Έν•œ κ·Έλž˜ν”„λ‘œ, 사이클이 μ—†λŠ” κ·Έλž˜ν”„μ΄λ‹€.


Reference