กราฟหนาแน่น
ในคณิตศาสตร์ กราฟหนาแน่น คือกราฟซึ่งมีจำนวนเส้นเชื่อมมาก (จำนวนเส้นเชื่อมใกล้เคียงกับจำนวนเส้นเชื่อมของกราฟบริบูรณ์) ในทางกลับกัน กราฟไม่หนาแน่น คือที่มีจำนวนเส้นเชื่อมน้อย
สำหรับกราฟไม่ระบุทิศทาง ความหนาแน่นของกราฟหาได้จาก
จำนวนเส้นเชื่อมที่มากที่สุดคือ ½ |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.