fbpx
วิกิพีเดีย

กราฟหนาแน่น

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

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

จำนวนเส้นเชื่อมที่มากที่สุดคือ ½ |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.

กราฟหนาแน, ในคณ, ตศาสตร, อกราฟซ, งม, จำนวนเส, นเช, อมมาก, จำนวนเส, นเช, อมใกล, เค, ยงก, บจำนวนเส, นเช, อมของกราฟบร, รณ, ในทางกล, บก, กราฟไม, หนาแน, อท, จำนวนเส, นเช, อมน, อยสำหร, บกราฟไม, ระบ, ศทาง, ความหนาแน, นของกราฟหาได, จาก, displaystyle, frac, จำนวนเส, นเ. inkhnitsastr krafhnaaenn khuxkrafsungmicanwnesnechuxmmak canwnesnechuxmiklekhiyngkbcanwnesnechuxmkhxngkrafbriburn inthangklbkn krafimhnaaenn khuxthimicanwnesnechuxmnxysahrbkrafimrabuthisthang khwamhnaaennkhxngkrafhaidcak D 2 E V V 1 displaystyle D frac 2 E V V 1 canwnesnechuxmthimakthisudkhux V V 1 dngnnkhwamhnaaennkhxngkrafthimakthisudkhux 1 krafbriburn aelakhwamhnaaennkhxngkrafthinxythisudkhux 0 Coleman amp More 1983 xangxing aekikhPaul E Black Sparse graph from Dictionary of Algorithms and Data Structures Paul E Black ed NIST Retrieved on 29 September 2005 Coleman Thomas F More 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 amp Sons ISBN 0 471 24134 2 Ossona de Mendez Patrice Nesetril 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 ekhathungcak https th wikipedia org w index php title krafhnaaenn amp oldid 4698196, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,

บทความ

, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม