유향 그래프

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

유향 그래프는 ${\displaystyle \Gamma =(V,E)}$는 집합 ${\displaystyle V}$와, ${\displaystyle V}$의 순서쌍들로 구성된 집합 ${\displaystyle E\subset V\times V}$의 순서쌍이다. 이 경우, ${\displaystyle e=(u,v)}$라면 ${\displaystyle e}$를 ${\displaystyle u}$에서 ${\displaystyle v}$로 가는 변이라고 하며, 꼭짓점 ${\displaystyle v}$는 변 ${\displaystyle e}$의 머리(영어: head 헤드^[*], 꼭짓점 ${\displaystyle u}$는 변 ${\displaystyle e}$의 꼬리(영어: tail 테일^[*])라고 한다.

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

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

위키미디어 공용에 유향 그래프 주제와 관련된 미디어 분류가 있습니다.

• 그래프 이론
• 그래프
• 그래프 이론 용어
• 네트워크 이론

이 글은 수학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다.