1. 개요
순환 구조를 가지는 그래프는 간선의 방향성 여부에 따라 무방향, 방향 그래프로 분류할 수 있다.
이때 방향 그래프와 무방향 그래프에서 노드의 개수가 N으로 주어졌을때 최대 간선의 개수를 구할 수 있다.
2. 방향 그래프에서의 최대 간선의 수
방향 그래프에서 간선의 개수를 최대로 하려면, 각 노드가 자신의 노드를 제외한 나머지 노드와 모두 이어져야 하며 이때 두 방향 모두 존재할때 최대 갯수의 간선을 가진다.
이에 따르면,
노드 1번에서 가질 수 있는 간선의 수 : 2(N-1)
노드 2번에서 가질 수 있는 간선의 수 : 2(N-2)
노드 3번에서 가질 수 있는 간선의 수 : 2(N-3)
이를 모두 더하면
2(N-1 + N-2 + N-3 + .... + N-N)
2*(N^2 - (N(N+1)/2))
= N(N-1)
3. 무방향 그래프에서의 최대 간선의 수
무방향은 위 경우에서 중복하는 화살표를 모두 제거한 경우이므로, 그대로 나누기 2를 하면 된다.
= N(N-1)/2
