소프트웨어개발 - 그래프 (무방향, 방향 최대 수 구하는 공식)

#0 용어

 

* 정점 - 쓰이는 위치마다 다르겠지만, 최소한에 소프트웨어 개발에서는 "노드"라고 생각하면 됨

* 간선 - 각 노드를 이어주는 선

 

#1 무방향 그래프

 

- 두 *정점을 연결하는 *간선에  방향이 없는 그래프

- *정점이 n개인 무방향 그래프에서 최대의 *간선 수 구하는 공식 = n(n-1)/2

- 마지막에 2를 나눠주는 이유는 하나의 간선으로 (방향이 없으니깐) 주고 받는게 가능하다.

 

#2 방향 그래프

 

- *간선에 방향이 있는 그래프

- *정점이 n개인 방향 그래프의 최대 *간선 수 구하는 공식 = n(n-1)

- 방향이 지정된 경우, 하나의 방향당 한번씩만 사용이 가능하다고 보면 된다.(한번은 아니지만 아무튼 같은방향으로 가는 횟수를 1번이라고 가정)