กราฟหนาแน่น

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

สำหรับกราฟไม่ระบุทิศทาง ความหนาแน่นของกราฟหาได้จาก

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

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

อ้างอิง

• Paul E. Black, Sparse graph, from Dictionary of Algorithms and Data Structures, Paul E. Black (ed.), NIST. Retrieved on 29 September 2005.
• แม่แบบ:Citation.
• แม่แบบ:Citation.
• แม่แบบ:Citation.
• แม่แบบ:Cite conference
• แม่แบบ:Citation.