유향 그래프

(외차수에서 넘어옴)

유향 그래프(有向graph, 영어: directed graph 또는 digraph)는 방향을 가진 그래프이다. 방향 그래프라고도 한다.

단순한 방향 그래프.

정의 편집

유향 그래프 는 집합  와,  의 순서쌍들로 구성된 집합  의 순서쌍이다. 이 경우,  라면   에서  로 가는 변이라고 하며, 꼭짓점  는 변  머리(영어: head 헤드[*], 꼭짓점  는 변  꼬리(영어: tail 테일[*])라고 한다.

용도 편집

유향 그래프로 나타내는 것에는 먹이그물[1]게임 트리 등이 있다.

내차수와 외차수 편집

정점의 경우 정점에 인접한 머리 끝부분의 수를 정점의 내차수(indegree)라고 하며 정점에 인접한 꼬리의 끝부분의 수를 외차수(outdegree)라고 부른다.

같이 보기 편집

각주 편집