그래프에서는 간선이 많은 그래프와 그렇지 않은 그래프를 구분한다. 간선이 많은 그래프는 밀집 그래프(dense graph)라고 하고, 그렇지 않은 그래프는 희소 그래프(sparse graph)라고 한다. 극단적으로 임의의 노드가 다른 모든 노드에 연결된 그래프가 있다. 이런 그래프를 완전 그래프(complete graph)라고 하며, 그림 2-11에서 왼쪽에 해당한다.

▲ 그림 2-11 완전 그래프와 희소 그래프

 

완전 그래프에는 많은 간선이 있다. 완전 그래프에 n개의 노드가 있다면 모든 노드가 다른 n - 1개의 노드에 연결되므로 모든 그래프에는 n(n - 1)/2개의 간선이 있다. 일반적으로 n개의 노드가 있는 그래프의 간선 수가 n²에 근접할수록 조밀하다고 하고, 간선 수가 약 n개라면 성기다고 한다. n과 n² 사이에 모호한 영역이 있지만, 통상적으로 희소 그래프인지 밀집 그래프인지는 응용 프로그램의 문맥을 통해 알 수 있다. 사실 대부분 응용 프로그램은 희소 그래프를 사용한다. 예를 들어, 사람 사이의 친구 관계를 표현하는 그래프를 다룬다고 해 보자. 이 지구의 모든 이가 그래프에 표현된다고 가정하면 약 70억 또는 n = 7 × 10⁹개의 노드를 갖는 그래프가 만들어진다. 또한, 모든 사람이 1,000명의 친구와 연결된다고 가정하면(아마도 불가능하겠지만) 간선의 수는 7 × 10¹² 또는 7조가 된다. n = 7 × 10⁹일 때 n(n - 1)/2의 수는 약 2.5 × 10¹⁹ 또는 25퀀틸리언(quintillion)(10¹⁸)이 된다. 이는 7조보다 훨씬 큰 수다. 따라서 그래프는 대량의 간선이 있지만, 여전히 성긴 구조가 된다.