- 그래프의 개념
- 그래프 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) : 진입차수 + 진출차수
- 단순 경로 : 경로상의 모든 정점이 다른 경우
- 단순 순회 : 모든 간선이 다르고 시작점과 끝점은 같은 경로
|
|