เหตุใดเส้นผ่านศูนย์กลางของกราฟแบบสุ่มจึงมีความสำคัญ?
ฉันสามารถดูเส้นผ่านศูนย์กลางของกราฟซึ่งกำหนดเป็นความยาวของเส้นทางที่สั้นที่สุดที่ยาวที่สุดคือปริมาณที่ไม่สำคัญในกราฟสุ่มเช่นกราฟสุ่ม$G(n,p)$ เกิดจากการเพิ่มขอบระหว่าง $n$ ชี้อย่างอิสระด้วยความน่าจะเป็น $p$.
แต่อะไรที่ทำให้มันมีความสำคัญทางคณิตศาสตร์? มันมีความสัมพันธ์อะไรกับแนวคิดกราฟพื้นฐานอื่น ๆ ? ยิ่งไปกว่านั้นถ้าฉันเพิ่มข้อ จำกัด บางอย่างบนกราฟเช่นการแจกแจงองศาหรือข้อ จำกัด เชิงพื้นที่บนจุดยอด (เช่นกราฟเรขาคณิตแบบสุ่ม) สิ่งนี้จะทำอย่างไรกับความสำคัญของเส้นผ่านศูนย์กลางกราฟ
คำตอบ
เส้นผ่านศูนย์กลางของกราฟมีความสำคัญในตัวมันเองเช่นเดียวกับจำนวนสีหรือระดับสูงสุด หากคุณต้องการให้กราฟของคุณสร้างแบบจำลองเครือข่ายก็จะบอกคุณถึงจำนวนสูงสุดของ 'hops' ที่ต้องใช้เพื่อรับจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง หากกราฟของคุณฝังอยู่ในรูปทรงเรขาคณิตเช่นกราฟที่ขอบแต่ละด้านเป็นเส้นตรงของความยาว 1 จากนั้นเส้นผ่านศูนย์กลางของกราฟ (นามธรรม) คือขอบเขตบนของเส้นผ่านศูนย์กลางของกราฟที่ฝังซึ่งถือเป็นส่วนย่อยของ$\mathbb{R}^n$.
ปล่อย $D$ เป็นเส้นผ่านศูนย์กลางของกราฟ $n$ คำสั่งของมัน $\Delta$ ระดับสูงสุดและ $\kappa$การเชื่อมต่อ การวิเคราะห์พฤติกรรมทั่วไปบางประการสำหรับการทำงานของเส้นผ่านศูนย์กลาง (เป็นแนวโน้มไม่ใช่ทฤษฎีบท):
- หากกราฟมีเส้นผ่านศูนย์กลางต่ำและมีจุดยอดจำนวนมากก็จะต้องมีหลายขอบและขอบเหล่านี้จะต้องกระจายในลักษณะที่ 'สม่ำเสมอ' เพื่อไม่ให้จุดยอดทั้งสองอยู่ห่างกัน
- หากเส้นผ่านศูนย์กลางของกราฟมีขนาดใหญ่มากเมื่อเทียบกับจำนวนจุดยอดแสดงว่ากราฟมีขอบน้อยกว่า
- ในเส้นเลือดที่คล้ายกันกับจุดข้างต้นเส้นผ่านศูนย์กลางและระดับสูงสุดเข้าด้วยกันจะผูกมัดจำนวนจุดยอดทั้งหมดที่กราฟจะมีได้ ในทางทฤษฎีคุณจะไม่สามารถหาจุดยอดจากกราฟได้มากไปกว่าการสร้างต้นไม้แห่งความลึก$D$ ที่แตกแขนงออกไปอย่างคร่าวๆ $\Delta-1$ครั้งในแต่ละเลเยอร์โดยมีขอบพิเศษเล็กน้อยเพื่อปิดสิ่งต่างๆ การศึกษานี้ถูกผูกไว้เป็นหัวข้อของปัญหาเส้นผ่าศูนย์กลางศึกษาระดับปริญญา
- ในขณะที่เส้นผ่านศูนย์กลางและองศาสูงสุดถูกผูกไว้ $n$จากด้านบนเส้นผ่านศูนย์กลางและการเชื่อมต่อผูกไว้จากด้านล่าง ขอบเขตมีลักษณะประมาณ$n \geq \kappa \cdot (D-1)$.
- เส้นผ่านศูนย์กลางยัง จำกัด เส้นรอบวงของกราฟด้วย กล่าวโดยย่อคือถ้าเส้นผ่านศูนย์กลางต่ำและกราฟมีวัฏจักรใด ๆ ก็ต้องมีวัฏจักรของความยาวสั้น
ในที่สุดเส้นผ่านศูนย์กลางทำหน้าที่เป็นข้อ จำกัด ด้านความซับซ้อนที่ดี หากคุณกำลังพยายามศึกษาโครงสร้างหรือคุณลักษณะบางอย่างในกราฟทั่วไปและกำลังสูญเสียไปอย่างสิ้นหวังการพิจารณาสิ่งที่เกิดขึ้นในกราฟที่มีเส้นผ่านศูนย์กลาง 2 เป็นสิ่งที่มีประโยชน์ (โดยเฉพาะอย่างยิ่งเมื่อพิจารณาจากข้อ จำกัด อื่น ๆ หรือคลาสกราฟที่ จำกัด เพื่อใช้ร่วมกับมัน) ซึ่งทำให้บังเอิญว่ากราฟเกือบทั้งหมดมีเส้นผ่านศูนย์กลาง 2!