Skip to content

Latest commit

Β 

History

History
65 lines (45 loc) Β· 3.24 KB

graph.md

File metadata and controls

65 lines (45 loc) Β· 3.24 KB
Raw

κ·Έλž˜ν”„

κ·Έλž˜ν”„λŠ” μ‹€μ œ μ„Έκ³„μ˜ ν˜„μƒμ΄λ‚˜ 사물을 정점(Vertex) λ˜λŠ” λ…Έλ“œ(Node) 와 κ°„μ„ (Edge)둜 ν‘œν˜„ν•˜κΈ° μœ„ν•΄ μ‚¬μš©

λ…Έλ“œ(Node) = 정점(Vertex) κ°„μ„ (Edge) = link = branch

κ·Έλž˜ν”„ (Graph) κ΄€λ ¨ μš©μ–΄

  • λ…Έλ“œ (Node): μœ„μΉ˜λ₯Ό 말함, 정점(Vertex)라고도 함
  • κ°„μ„  (Edge): μœ„μΉ˜ κ°„μ˜ 관계λ₯Ό ν‘œμ‹œν•œ μ„ μœΌλ‘œ λ…Έλ“œλ₯Ό μ—°κ²°ν•œ 선이라고 보면 됨 (link λ˜λŠ” branch 라고도 함)
  • 인접 정점 (Adjacent Vertex)(μΈμ ‘λ…Έλ“œ) : κ°„μ„ μœΌλ‘œ 직접 μ—°κ²°λœ 정점(λ˜λŠ” λ…Έλ“œ)
  • μ •μ μ˜ 차수 (Degree): 무방ν–₯ κ·Έλž˜ν”„μ—μ„œ ν•˜λ‚˜μ˜ 정점에 μΈμ ‘ν•œ μ •μ μ˜ 수
  • μ§„μž… 차수 (In-Degree): λ°©ν–₯ κ·Έλž˜ν”„μ—μ„œ μ™ΈλΆ€μ—μ„œ μ˜€λŠ” κ°„μ„ μ˜ 수
  • μ§„μΆœ 차수 (Out-Degree): λ°©ν–₯ κ·Έλž˜ν”„μ—μ„œ μ™ΈλΆ€λ‘œ ν–₯ν•˜λŠ” κ°„μ„ μ˜ 수
  • 경둜 길이 (Path Length): 경둜λ₯Ό κ΅¬μ„±ν•˜κΈ° μœ„ν•΄ μ‚¬μš©λœ κ°„μ„ μ˜ 수
  • λ‹¨μˆœ 경둜 (Simple Path): 처음 정점과 끝 정점을 μ œμ™Έν•˜κ³  μ€‘λ³΅λœ 정점이 μ—†λŠ” 경둜
  • 사이클 (Cycle): λ‹¨μˆœ 경둜의 μ‹œμž‘ 정점과 μ’…λ£Œ 정점이 λ™μΌν•œ 경우

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

무방ν–₯ κ·Έλž˜ν”„ (Undirected Graph)

  • λ°©ν–₯이 μ—†λŠ” κ·Έλž˜ν”„ (간선에 ν™”μ‚΄ν‘œκ°€ μ—†λŠ” κ·Έλž˜ν”„)
  • 간선을 톡해, λ…Έλ“œλŠ” μ–‘λ°©ν–₯으둜 갈 수 있음
  • 보톡 λ…Έλ“œ A, Bκ°€ μ—°κ²°λ˜μ–΄ μžˆμ„ 경우, (A, B) λ˜λŠ” (B, A) 둜 ν‘œκΈ°

λ°©ν–₯ κ·Έλž˜ν”„ (Directed Graph)

  • 간선에 λ°©ν–₯이 μžˆλŠ” κ·Έλž˜ν”„ (간선에 ν™”μ‚΄ν‘œκ°€ μžˆλŠ” κ·Έλž˜ν”„)
  • 보톡 λ…Έλ“œ A, Bκ°€ A -> B 둜 κ°€λŠ” κ°„μ„ μœΌλ‘œ μ—°κ²°λ˜μ–΄ μžˆμ„ 경우, <A, B> 둜 ν‘œκΈ° (<B, A> λŠ” B -> A 둜 κ°€λŠ” 간선이 μžˆλŠ” κ²½μš°μ΄λ―€λ‘œ <A, B> 와 닀름)

κ°€μ€‘μΉ˜ κ·Έλž˜ν”„ (Weighted Graph) λ˜λŠ” λ„€νŠΈμ›Œν¬ (Network)

  • 간선에 λΉ„μš© λ˜λŠ” κ°€μ€‘μΉ˜κ°€ ν• λ‹Ήλœ κ·Έλž˜ν”„

μ—°κ²° κ·Έλž˜ν”„ (Connected Graph) 와 λΉ„μ—°κ²° κ·Έλž˜ν”„ (Disconnected Graph)

  • μ—°κ²° κ·Έλž˜ν”„ (Connected Graph)
    • 무방ν–₯ κ·Έλž˜ν”„μ— μžˆλŠ” λͺ¨λ“  λ…Έλ“œμ— λŒ€ν•΄ 항상 κ²½λ‘œκ°€ μ‘΄μž¬ν•˜λŠ” 경우
  • λΉ„μ—°κ²° κ·Έλž˜ν”„ (Disconnected Graph)
    • 무방ν–₯ κ·Έλž˜ν”„μ—μ„œ νŠΉμ • λ…Έλ“œμ— λŒ€ν•΄ κ²½λ‘œκ°€ μ‘΄μž¬ν•˜μ§€ μ•ŠλŠ” 경우

사이클 (Cycle) κ³Ό λΉ„μˆœν™˜ κ·Έλž˜ν”„ (Acyclic Graph)

  • 사이클 (Cycle)
    • λ‹¨μˆœ 경둜의 μ‹œμž‘ λ…Έλ“œμ™€ μ’…λ£Œ λ…Έλ“œκ°€ λ™μΌν•œ 경우
  • λΉ„μˆœν™˜ κ·Έλž˜ν”„ (Acyclic Graph)
    • 사이클이 μ—†λŠ” κ·Έλž˜ν”„

μ™„μ „ κ·Έλž˜ν”„ (Complete Graph)

  • κ·Έλž˜ν”„μ˜ λͺ¨λ“  λ…Έλ“œκ°€ μ„œλ‘œ μ—°κ²°λ˜μ–΄ μžˆλŠ” κ·Έλž˜ν”„

κ·Έλž˜ν”„μ™€ 트리의 차이

  • νŠΈλ¦¬λŠ” κ·Έλž˜ν”„ 쀑에 μ†ν•œ νŠΉλ³„ν•œ μ’…λ₯˜λΌκ³  λ³Ό 수 있음
κ·Έλž˜ν”„ 트리
μ •μ˜ λ…Έλ“œμ™€ λ…Έλ“œλ₯Ό μ—°κ²°ν•˜λŠ” κ°„μ„ μœΌλ‘œ ν‘œν˜„λ˜λŠ” 자료 ꡬ쑰 κ·Έλž˜ν”„μ˜ ν•œ μ’…λ₯˜, λ°©ν–₯성이 μžˆλŠ” λΉ„μˆœν™˜ κ·Έλž˜ν”„
λ°©ν–₯μ„± λ°©ν–₯ κ·Έλž˜ν”„, 무방ν–₯ κ·Έλž˜ν”„ λ‘˜λ‹€ μ‘΄μž¬ν•¨ λ°©ν–₯ κ·Έλž˜ν”„λ§Œ μ‘΄μž¬ν•¨
사이클 사이클 κ°€λŠ₯함, μˆœν™˜ 및 λΉ„μˆœν™˜ κ·Έλž˜ν”„ λͺ¨λ‘ μ‘΄μž¬ν•¨ λΉ„μˆœν™˜ κ·Έλž˜ν”„λ‘œ 사이클이 μ‘΄μž¬ν•˜μ§€ μ•ŠμŒ
루트 λ…Έλ“œ 일반적으둜 루트 λ…Έλ“œ μ‘΄μž¬ν•˜μ§€ μ•ŠμŒ 루트 λ…Έλ“œ μ‘΄μž¬ν•¨
λΆ€λͺ¨/μžμ‹ 관계 일반적으둜 λΆ€λͺ¨ μžμ‹ κ°œλ…μ΄ μ‘΄μž¬ν•˜μ§€ μ•ŠμŒ λΆ€λͺ¨ μžμ‹ 관계가 μ‘΄μž¬ν•¨