| 종류 |

  • 그래프의 개념
    • 그래프 G는 하나 이상의 "정점(노드)들의 집합 V" 와 "두 정점의 쌍으로 구성되는 간선(링크)들의 집합 E" 로 이루어지며, G=(V, E) 로 표현한다. 또한, V(G)는 그래프 G를 구성하는 정점들의 집합이고, E(G)는 간선들의 집합이다.
    • 간선으로 연결된 두 정점은 인접(adjacent)한다.
    • 간선은 가중치(weight) 또는 비용(cost)을 가질 수 있다.
  • 주요 개념
    • 인접(adjacent) : (V1,V2)가 E(G)에 있는 간선이면, V1 과 V2는 인접
    • 경로(Path) : 두 정점 사이 간선으로 연결된 일련의 정점
    • 루프(loop) : (V,V)처럼 자기 자신으로 되돌아오는 간선
    • 사이클(cycle) :  경로의 시작점과 끝점이 같은 경우
    • 진입차수(in-degree) : 임의 노드에 들어오는 간선의 수
    • 진출차수(out-degree) : 임의 노드에서 나가는 간선의 수
    • 차수(degree) : 진입차수 + 진출차수
    • 단순 경로 : 경로상의 모든 정점이 다른 경우
    • 단순 순회 : 모든 간선이 다르고 시작점과 끝점은 같은 경로