밀집 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:GraphQL Logo.svg|thumb]]
[[수학]]에서 '''밀집 그래프'''(dense graph)는 간선(변)의 수가 최대 간선의 수에 가까운 [[그래프]]이다. 그와 반대로, 간선이 얼마 없는 그래프는 '''희소 그래프'''(sparse graph)라고 한다. 밀집과 희소 간의 구별은 다소 모호하므로 문맥에 따라 달라질 수 있다.

방향이 없는 무향 단순 그래프의 경우 '''그래프 밀도'''는 다음과 같이 정의된다:
:<math>D = \frac{2|E|}{|V|\,(|V|-1)}</math>

방향이 있는 유향 단순 그래프의 경우, 그래프 밀도는 다음과 같이 정의된다:
:<math>D = \frac{|E|}{|V|\,(|V|-1)}</math>

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

== 참고 문헌 ==
* {{인용| first1 = Thomas F. | last1 = Coleman | first2 = Jorge J. | last2 = Moré | year = 1983 | title = Estimation of sparse Jacobian matrices and graph coloring Problems | journal = SIAM Journal on Numerical Analysis | volume = 20 | pages = 187–209 | doi = 10.1137/0720013 | issue = 1 }}. <!-- feel free to replace with a better reference for "graph density" -->

{{토막글|수학}}

[[분류:그래프족]]