กราฟหนาแน่น

จากวิกิพีเดีย สารานุกรมเสรี

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

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

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

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


อ้างอิง[แก้]

  • Paul E. Black, Sparse graph, from Dictionary of Algorithms and Data Structures, Paul E. Black (ed.), NIST. Retrieved on 29 September 2005.
  • 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 .
  • Diestel, Reinhard (2005), Graph Theory, Graduate Texts in Mathematics, Springer-Verlag, ISBN 3540261834, OCLC 181535575 .
  • Preiss, Bruno (1998), Data Structures and Algorithms with Object-Oriented Design Patterns in C++, John Wiley & Sons, ISBN 0-471-24134-2 .
  • Ossona de Mendez, Patrice; Nešetřil, Jaroslav (2010). "From Sparse Graphs to Nowhere Dense Structures: Decompositions, Independence, Dualities and Limits". European Congress of Mathematics. European Mathematical Society. pp. 135–165. 
  • Streinu, I.; Theran, L. (2009), "Sparse hypergraphs and pebble game algorithms", European Journal of Combinatorics 30 (8): 1944–1964, arXiv:math/0703921, doi:10.1016/j.ejc.2008.12.018 .