์ฉ์ด
- ์ ์ (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)
- ์ฌ์ดํด์ด ์๋ ์ฐ๊ฒฐ ๊ทธ๋ํ
- ๊ฐ์ ์ ์ ์ ๊ฐ์ง๋ ํธ๋ฆฌ๋ ๊ฐ์ ๊ฐ์ ์ ๊ฐ์ง๋ค.