-graph-

graph는 tree를 포함하는 개념

G(graph) = (V(노드[vertex]들의 집합), E(선[edge]들의 집합)

Edge를 서로 다른 vertex에 연결시켜야 한다.

※vertex와 edge가 따로 있는 경우나 아예 없는 경우도 graph이다.

directed graph : 방향이 있는 벡터 방식의 edge가 있는 graph (<-> undirected graph : no oriented)

ex) <a, b> ≠ <b, a> (a, b) = (b, a)

directed graph -> vertex가 n개인 graph에서 하나의 vertex에서 가질 수 있는 최대 edge의 개수는 n(n-1)개가 된다.

undirected graph -> 최대 edge 개수는 n(n-1)/2개

이때, 최대 edge 개수를 갖는 graph를 completed directed/undirected graph라 한다.

만약, vertex a, b가 하나의 edge로 연결되어 있다면 a와 b는 인접(adjacent)한다.

a -> b : vertex a is adjacent to b,	b is adjacent from a