อ่าน 2 นาที
สัมประสิทธิ์ความเชื่อมโยง
ในทฤษฎีกราฟสัมประสิทธิ์ความเชื่อมโยงเป็นค่าคงที่ของกราฟระนาบที่วัดจำนวนหน้าที่มีขอบเขตของกราฟ โดยคิดเป็นเศษส่วนของจำนวนหน้าที่เป็นไปได้สำหรับกราฟระนาบอื่นที่มีจำนวนจุดยอดเท่ากัน...
สัมประสิทธิ์ความเชื่อมโยง
ในทฤษฎีกราฟสัมประสิทธิ์ความเชื่อมโยงเป็นค่าคงที่ของกราฟระนาบที่วัดจำนวนหน้าที่มีขอบเขตของกราฟ โดยคิดเป็นเศษส่วนของจำนวนหน้าที่เป็นไปได้สำหรับกราฟระนาบอื่นที่มีจำนวนจุดยอดเท่ากัน มีค่าตั้งแต่ 0 สำหรับต้นไม้ไปจนถึง 1 สำหรับกราฟระนาบสูงสุด[ 1 ] [ 2 ]
คำนิยาม
สัมประสิทธิ์ความเชื่อมโยงใช้เพื่อเปรียบเทียบโครงสร้างวงจรทั่วไปของกราฟระนาบที่เชื่อมต่อกับข้อมูลอ้างอิงที่เกี่ยวข้องสุดขั้วสองแบบ ในด้านหนึ่งคือต้นไม้ ซึ่งเป็น กราฟระนาบที่ไม่มีวงจร[ 1 ]อีกด้านหนึ่งคือกราฟระนาบสูงสุดซึ่งเป็นกราฟระนาบที่มีจำนวนขอบและหน้าสูงสุดที่เป็นไปได้สำหรับจำนวนจุดยอดที่กำหนด สัมประสิทธิ์ความเชื่อมโยงแบบปกติคืออัตราส่วนของวงจรหน้าที่มีอยู่ต่อจำนวนวงจรหน้าสูงสุดที่เป็นไปได้ในกราฟ อัตราส่วนนี้เป็น 0 สำหรับต้นไม้และ 1 สำหรับกราฟระนาบสูงสุดใดๆ
โดยทั่วไปแล้ว สามารถแสดงได้โดยใช้ลักษณะเฉพาะของออยเลอร์ ว่า กราฟระนาบ ที่มี n จุดยอด ทั้งหมด จะมีหน้าที่มีขอบเขตอย่างมากที่สุด 2n − 5 หน้า (ไม่นับหน้าที่ไม่มีขอบเขตหนึ่งหน้า) และถ้ามี ขอบ mเส้น จำนวนหน้าที่มีขอบเขตจะเป็นm − n + 1 (เท่ากับอันดับวงจรของกราฟ) ดังนั้น สัมประสิทธิ์การเชื่อมต่อแบบปกติสามารถกำหนดได้จากอัตราส่วนของตัวเลขทั้งสองนี้:
ค่านี้จะแตกต่างกันไป ตั้งแต่ 0 สำหรับต้นไม้ ไปจนถึง 1 สำหรับกราฟระนาบสูงสุด
แอปพลิเคชัน
สัมประสิทธิ์ความเชื่อมโยงสามารถใช้ในการประเมินความซ้ำซ้อนของเครือข่าย พารามิเตอร์นี้ร่วมกับการเชื่อมต่อเชิงพีชคณิตซึ่งวัดความแข็งแกร่งของเครือข่าย อาจใช้ในการวัดปริมาณลักษณะทางโทโพโลยีของความยืดหยุ่นของเครือข่ายในเครือข่ายการจ่ายน้ำ[ 3 ]นอกจากนี้ยังใช้ในการกำหนดลักษณะโครงสร้างเครือข่ายของถนนในเขตเมือง[ 4 ] [ 5 ] [ 6 ]
ข้อจำกัด
จากการใช้คำจำกัดความของดีกรีเฉลี่ยจะเห็นได้ว่าในกราฟขนาดใหญ่ (จำนวนขอบ)ความเป็นตาข่ายมีแนวโน้มเข้าใกล้
ดังนั้น สำหรับกราฟขนาดใหญ่ ความเป็นเครือข่ายจึงไม่ได้ให้ข้อมูลมากกว่าระดับเฉลี่ยของดีกรี
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ สัมประสิทธิ์ความเชื่อมโยง
ในทฤษฎีกราฟสัมประสิทธิ์ความเชื่อมโยงเป็นค่าคงที่ของกราฟระนาบที่วัดจำนวนหน้าที่มีขอบเขตของกราฟ โดยคิดเป็นเศษส่วนของจำนวนหน้าที่เป็นไปได้สำหรับกราฟระนาบอื่นที่มีจำนวนจุดยอดเท่ากัน...
คำนิยาม
สัมประสิทธิ์ความเชื่อมโยงใช้เพื่อเปรียบเทียบโครงสร้างวงจรทั่วไปของกราฟระนาบที่เชื่อมต่อกับข้อมูลอ้างอิงที่เกี่ยวข้องสุดขั้วสองแบบ ในด้านหนึ่งคือ ต้นไม้ ซึ่งเป็น กราฟระนาบที่ไม่มีวงจร [ 1 ] อีกด้านหนึ่งคือ กราฟระนาบสูงสุด...
แอปพลิเคชัน
สัมประสิทธิ์ความเชื่อมโยงสามารถใช้ในการประเมินความซ้ำซ้อนของเครือข่าย พารามิเตอร์นี้ร่วมกับ การเชื่อมต่อเชิงพีชคณิต ซึ่งวัดความแข็งแกร่งของเครือข่าย อาจใช้ในการวัดปริมาณลักษณะทางโทโพโลยีของความยืดหยุ่นของเครือข่ายในเครือข่ายการจ่ายน้ำ [ 3 ]...
ข้อจำกัด
จากการใช้คำจำกัดความของดีกรีเฉลี่ยจะเห็นได้ว่าในกราฟขนาดใหญ่ (จำนวนขอบ ) ความเป็นตาข่ายมีแนวโน้มเข้าใกล้ ⟨ เค ⟩ = 2 ม / n {\displaystyle \langle k\rangle =2m/n} n ≫ 1 {\displaystyle n\gg 1}