방향 그래프

무방향 그래프가 있다는 것은 방향 그래프도 있다는 이야기이겠지요. 다음 그림은 방향 그래프입니다.

▲ 그림 6-2 방향 그래프

방향 그래프는 다음과 같이 표기하겠습니다.

G = <V, E>

V(G) = {0, 1, 2, 3}

E(G) = {<0, 1>, <0, 2>, <1, 2>, <2, 3>, <3, 2>}

그림 6-2를 보면 0과 2 사이에 화살표가 있습니다. 이는 0에서 출발하여 2로 도착합니다. 이때 0은 tail이 되고 2는 head가 됩니다. 그리고 <0, 2>라고 표기합니다. 무방향과 비교하면 표기법이 다르지요. 방향이 있으므로 <2, 3>과 <3, 2>는 다릅니다. 그림을 보면 쉽게 알 수 있지요. 이 특징을 이용하여 수식을 하나 도출해 보면 정점 개수가 n개일 때 최대 에지 개수는 n*(n-1)입니다.