กราฟหนาแน่น

ในคณิตศาสตร์ กราฟหนาแน่น คือกราฟซึ่งมีจำนวนเส้นเชื่อมมาก (จำนวนเส้นเชื่อมใกล้เคียงกับจำนวนเส้นเชื่อมของกราฟบริบูรณ์)
ในทางกลับกัน กราฟไม่หนาแน่น คือที่มีจำนวนเส้นเชื่อมน้อย

สำหรับกราฟไม่ระบุทิศทาง ความหนาแน่นของกราฟหาได้จาก
 
จำนวนเส้นเชื่อมที่มากที่สุดคือ ½ |V| (|V|−1) ดังนั้นความหนาแน่นของกราฟที่มากที่สุดคือ 1 (กราฟบริบูรณ์) และความหนาแน่นของกราฟที่น้อยที่สุดคือ 0 .

อ้างอิง 
 Paul E. Black, Sparse graph, from Dictionary of Algorithms and Data Structures, Paul E. Black (ed.), NIST. Retrieved on 29 September 2005.
 . 
 .
 .
 
 .

ตระกูลกราฟ