Overview

Directed Graph는 하나의 노드에서 다른 노드로 일방통행하는 그래프이다. Undirected Graph는 방향이 없는 것이 아니라 양방향 그래프이다.

Directed Graph

Directed Graph 또는 digraph (방향 그래프)는 방향을 가진 그래프이다.

• $G = (V,E)$
• $E$는 $V$의 순서쌍으로 구성된다.
• $e$를 $u$에서 $v$로 가는 edge라고 하면, $e=(u,v)$로 표기하며, $v$는 head(머리), $u$는 tail(꼬리)라고 한다.
• (참고) 이전까지는 모두 Undirected graph를 다루었다.

Loop, Multiple edges

정의는 undirected graph의 경우와 동일하다. 다만, 방향이 존재한다.

Path and Cycle

정의는 undirected graph의 경우와 동일하다. 다만, 방향이 존재하기 때문에 $e=(u,v)$인 경우 $u$에서 $v$로만 이동이 가능하다. (역주행 불가능)

Adjacent Matrix

정의는 undirected graph의 경우와 동일하다. 다만, 방향에 맞게 $a_{ij}$를 정의해야 한다.

Directed Acyclic Graph

Directed acyclic graph(방향 비순환 그래프 ; DAG)는 cycle이 없는 directed graph이다.