1. 간선 / 연결선 / 가지의 종류 ☞ 노드 및 가지 참조
ㅇ 연결선의 방향(direction) 여부 ☞ 그래프 종류 (방향 그래프, 무방향 그래프)
- 방향 간선 (Directed Edge)
. 순서가 정해진 두 정점의 쌍
. 표기 : 방향 있는 두 정점 v,u 사이의 연결선을 < v, u >로 표시
. 例) 일방통행 도로
- 무 방향 간선 (Undirected Edge)
. 순서 없는 두 정점의 쌍
. 표기 : 방향 없는 두 정점 v,u 사이의 연결선을 ( v, u )로 표시
. 例) 기차의 철로
ㅇ 연결선의 가중치(weight) 여부 ☞ 그래프 종류 (가중치 그래프, 비 가중치 그래프)
- 연결선에 가중치(거리,시간,비용 등)를 부여할 수 있음
. 例) 도시들 간의 거리, 지점 간의 파이프 용량, 공항 간의 비행 시간(비용),
사람 간 친밀도 등
- [참고용어]
. 경로 (Path) : 어떤 정점에서 시작하여 특정 정점으로 끝나는 순회/방문/여정
. 경로 표현 : 두 정점 간을 잇는 간선 또는 정점들을 순서대로 나열하게됨 (중간에 비면 안됨)
. 경로 길이 (Path Length) : 떨어져 있는 두 정점 사이(경로)의 연결선 가중치들의 합
. 최단 경로 (Shortest Path) : 모든 가능한 경로 중 최소 경로 길이를 갖는 경로