์šฉ์–ด

  • ์ •์ (Vertex, Node): ๊ทธ๋ž˜ํ”„์˜ ๋…ธ๋“œ
  • ๊ฐ„์„ (Edge): ๊ทธ๋ž˜ํ”„์˜ ๋…ธ๋“œ๋ฅผ ์—ฐ๊ฒฐํ•˜๋Š” ์„ 
    • ๋ฐฉํ–ฅ (ํ™”์‚ดํ‘œ)
      • ๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„(Undirected Graph): ๊ฐ„์„ ์— ๋ฐฉํ–ฅ์ด ์—†๋Š” ๊ทธ๋ž˜ํ”„
      • ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„(Directed Graph): ๊ฐ„์„ ์— ๋ฐฉํ–ฅ์ด ์žˆ๋Š” ๊ทธ๋ž˜ํ”„
    • ๊ฐ’
      • ๊ฐ€์ค‘์น˜(Weight): ๊ฐ„์„ ์— ๋ถ€์—ฌ๋œ ๊ฐ’

์ •์˜

๊ทธ๋ž˜ํ”„(Graph)

๊ทธ๋ž˜ํ”„(graph) ๋Š” ์ •์ (vertex)์˜ ์ง‘ํ•ฉ ์™€ ๊ฐ„์„ (edge)์˜ ์ง‘ํ•ฉ ๋กœ ๊ตฌ์„ฑ๋œ๋‹ค.

  • ์€ ๋™๋“ฑํ•œ ๊ด€๊ณ„, ์ฆ‰, ํŠน์ • ๊ฐœ๋…์„ ์ •์˜ํ•  ๋•Œ ๋งŽ์ด ์‚ฌ์šฉํ•œ๋‹ค.
  • ์€ ๊ฐ’์ด ๊ฐ™์Œ์„, ์€ ํ•ด๋‹น ๊ฐœ๋…์˜ ์ •์˜ ์šฐ์ธก๊ณผ ๊ฐ™์Œ์„ ์˜๋ฏธํ•œ๋‹ค. ํ•ด๋‹น ์˜๋ฏธ๋ฅผ ๊ฐ•์กฐํ•œ๋‹ค.

Vertex

Edge

์ผ ๋•Œ, ๊ฐ„์„  ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜๋œ๋‹ค.

  • ๋Š” ๊ฐ๊ฐ ๊ฐ„์„  ์˜ ๋์ (Endpoint)์ด๋ผ ๋ถ€๋ฅธ๋‹ค.
  • ๋Š” ์„œ๋กœ ์ธ์ ‘ํ•œ๋‹ค(adjacent), ์ด์›ƒํ•œ๋‹ค(neighbors)๋ผ๊ณ  ํ•œ๋‹ค.
  • ๋Š” ๊ณผ ๋ฅผ ๋ถ™์–ด์žˆ๋‹ค(incident), ์—ฐ๊ฒฐํ•œ๋‹ค(connected)๋ผ๊ณ  ํ•œ๋‹ค.

๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„(Directed Graph)

  • ์œ„ ๊ทธ๋ž˜ํ”„์˜ ์ •์˜์—์„œ ์— ๋Œ€ํ•œ ์ •์˜๋ฅผ ์•„๋ž˜์™€ ๊ฐ™์ด ๋ฐ”๊พผ ๊ฒƒ์„ ๋งํ•œ๋‹ค.

  • ์ด์ „์— ๊ฐ„์„ ์˜ ์ •์˜๊ฐ€ ์ง‘ํ•ฉ์ด์—ˆ๋‹ค๋ฉด, ์ด์ œ๋Š” ์ˆœ์„œ์Œ์ด๋‹ค.

  • ๋Š” ๋ฐฉํ–ฅ๋ณ€(Directed Edge, arc)๋ผ ๋ถ€๋ฅธ๋‹ค.

  • ์€ ์‹œ์ (Start), ๋Š” ์ข…์ (End)์ด๋ผ ๋ถ€๋ฅธ๋‹ค.

๋‹ค์ค‘ ๊ทธ๋ž˜ํ”„(Multigraph)

๋‘ ์ •์  ์‚ฌ์ด์— ์—ฌ๋Ÿฌ ๊ฐ„์„ ์ด ์กด์žฌํ•  ์ˆ˜ ์žˆ๋Š” ๊ทธ๋ž˜ํ”„

๋‹ค์ค‘ ๊ทธ๋ž˜ํ”„ ๋Š” ์ •์ ์˜ ์ง‘ํ•ฉ , ๊ฐ„์„ ์˜ ์ง‘ํ•ฉ , ๊ฐ„์„ ์˜ ํ•จ์ˆ˜ ๋กœ ๊ตฌ์„ฑ๋œ๋‹ค.

  • ์ด์ „์—๋Š” ๊ฐ€ ๊ฐ„์„ ์˜ ์ง‘ํ•ฉ์ด์—ˆ์ง€๋งŒ, ์ด์ œ๋Š” ๊ฐ„์„ ์˜ ์ง‘ํ•ฉ์„ ์ •์˜ํ•˜๋Š” ํ•จ์ˆ˜ ๊ฐ€ ์ถ”๊ฐ€๋˜์—ˆ๋‹ค.
  • ๋Œ€์‹  ํ•จ์ˆ˜๋ฅผ ํ†ตํ•ด ์ด๋ฅผ ๊ณ„์‚ฐํ•œ๋‹ค.
  • ๋Š”, ๊ฐ„์„ ๊ณผ ์ด ๊ฐ„์„ ์ด ๊ฐ€์ง€๋Š” ๋์ ์„ ์‚ฌ์ƒํ•˜๋Š” ํ•จ์ˆ˜์ด๋‹ค.
  • ๊ณต์—ญ ๋Š” ํŠน์ • ์ง‘ํ•ฉ๋‚ด์˜ ๋ถ€๋ถ„์ง‘ํ•ฉ ์ค‘, ์›์†Œ์˜ ๊ฐœ์ˆ˜๋ฅผ 2๊ฐœ๋ฅผ ๊ฐ€์ง€๋Š” ์ง‘ํ•ฉ์ด๋‹ค.
  • ์ตœ์ข…์ ์œผ๋กœ ๊ฐ„์„ ๊ณผ ๋์ ์˜ ๊ด€๊ณ„๋Š” ์•„๋ž˜์™€ ๊ฐ™์ด ํ‘œํ˜„๋œ๋‹ค.

์œ ํ–ฅ ๋‹ค์ค‘ ๊ทธ๋ž˜ํ”„(Directed Multigraph)

์‚ฌ์ƒํ•˜๋Š” ํ•จ์ˆ˜์˜ ๊ณต์—ญ์ด ์›์†Œ๊ฐœ์ˆ˜๊ฐ€ 2๊ฐœ์ธ ์ง‘ํ•ฉ์กฑ์ด ์•„๋‹Œ, ์ˆœ์„œ์Œ์œผ๋กœ ์ •์˜ํ•˜๋ฉด ๋œ๋‹ค.

๊ฐ€์ค‘ ๊ทธ๋ž˜ํ”„(Weighted Graph)

๊ฐ„์„ ์— ๊ฐ€์ค‘์น˜๊ฐ€ ๋ถ€์—ฌ๋œ ๊ทธ๋ž˜ํ”„

  • ๊ฐ„์„ ์— ๋Œ€์‘๋˜๋Š” ๊ฐ’์„ ๊ณ„์‚ฐํ•˜๋Š” ํ•จ์ˆ˜๊ฐ€ ์ถ”๊ฐ€๋˜์—ˆ๋‹ค.

ํŠน์ˆ˜ํ•œ ๊ทธ๋ž˜ํ”„

์™„์ „ ๊ทธ๋ž˜ํ”„(Complete Graph)

  • ๋ชจ๋“  ์ •์ ์ด ์„œ๋กœ ์ธ์ ‘ํ•œ ๊ทธ๋ž˜ํ”„
  • ๊ผญ์ง“์ ์ด ๊ฐœ์ธ ๊ฒฝ์šฐ ์ด๋ผ๊ณ  ํ‘œํ˜„ํ•œ๋‹ค.
  • ๊ณ ๋“ฑํ•™๊ต๋•Œ ๋ฐฐ์šด ํŠน์ • ๋‹ค๊ฐํ˜•์˜ ๋ชจ๋“  ๋Œ€๊ฐ์„ ์ด์€ ๋ชจ์–‘์ด๋ผ ์ƒ๊ฐํ•˜๋ฉด ๋˜๊ฒ ๋‹ค.
  • ์€ ๊ฐœ์˜ ์ •์ ๊ณผ ๊ฐœ์˜ ๊ฐ„์„ ์„ ๊ฐ€์ง„๋‹ค.

์‚ฌ์ดํด ๊ทธ๋ž˜ํ”„(Cycle Graph)

  • ๊ฐ„์„ ์ด ๋ชจ๋‘ ํ•˜๋‚˜์˜ ์‚ฌ์ดํด์„ ์ด๋ฃจ๋Š” ๊ทธ๋ž˜ํ”„
  • ์ •์ ์ด ๊ฐœ์ธ ๊ฒฝ์šฐ ์ด๋ผ๊ณ  ํ‘œํ˜„ํ•œ๋‹ค.
  • ์€ ๊ฐœ์˜ ์ •์ ๊ณผ ๊ฐœ์˜ ๊ฐ„์„ ์„ ๊ฐ€์ง„๋‹ค.

ํŠธ๋ฆฌ(Tree)

  • ์‚ฌ์ดํด์ด ์—†๋Š” ์—ฐ๊ฒฐ ๊ทธ๋ž˜ํ”„
  • ๊ฐœ์˜ ์ •์ ์„ ๊ฐ€์ง€๋Š” ํŠธ๋ฆฌ๋Š” ๊ฐœ์˜ ๊ฐ„์„ ์„ ๊ฐ€์ง„๋‹ค.