밀집 그래프

수학에서 밀집 그래프(dense graph)는 간선(변)의 수가 최대 간선의 수에 가까운 그래프이다. 그와 반대로, 간선이 얼마 없는 그래프는 희소 그래프(sparse graph)라고 한다. 밀집과 희소 간의 구별은 다소 모호하므로 문맥에 따라 달라질 수 있다.

방향이 없는 무향 단순 그래프의 경우 그래프 밀도는 다음과 같이 정의된다:

$D={\frac {2|E|}{|V|\,(|V|-1)}}$

방향이 있는 유향 단순 그래프의 경우, 그래프 밀도는 다음과 같이 정의된다:

$D={\frac {|E|}{|V|\,(|V|-1)}}$

여기에서 E는 간선의 수, V는 그래프 안의 정점의 수이다. 무향 그래프의 간선의 최대 수는 $|V|(|V|-1)/2$이므로 최대 밀도는 1(완전 그래프의 경우)이며 최소 밀도는 0이다.(Coleman & Moré 1983)

참고 문헌

• Coleman, Thomas F.; Moré, Jorge J. (1983), “Estimation of sparse Jacobian matrices and graph coloring Problems”, 《SIAM Journal on Numerical Analysis》 20 (1): 187–209, doi:10.1137/0720013 .