ความเชื่อมโยง (ทฤษฎีกราฟ)
ในคณิตศาสตร์และวิทยาการคอมพิวเตอร์ เรื่องทฤษฎีกราฟ ความเชื่อมโยง (อังกฤษ: Connectivity) เป็นคุณสมบัติหนึ่งของกราฟ โดยหรือ กราฟเชื่อมโยง (Connected graph) หมายความว่ากราฟไม่มีส่วนที่แยกขาดจากกัน กล่าวคือ สำหรับทุก ๆ สองจุดยอดใด ๆ จะมีวิถีระหว่างจุดยอดทั้งสอง ในขณะที่ กราฟไม่เชื่อมโยง (Unconnected graph) หมายความว่ากราฟนั้นขาดออกจากกัน กล่าวคือมีอย่างน้อยสองจุดยอดที่ไม่มีวิถีระหว่างจุดยอดทั้งสองจุดนั้น
ความเชื่อมโยงของกราฟ ยังสามารถมองได้ในอีกแง่มุมหนึ่ง คือจำนวนของจุดยอดหรือเส้นเชื่อมที่น้อยที่สุด ที่ถ้าลบจุดยอดหรือเส้นเชื่อมเหล่านั้นทิ้งแล้ว กราฟดังกล่าวจะกลายเป็นกราฟไม่เชื่อมโยง[1] จะเห็นว่าความเชื่อมโยงของกราฟนั้นบ่งบอกถึงความแข็งแกร่ง/ความทนทานของกราฟ ตัวอย่างเช่นหากพิจารณาให้บ้านเป็นจุดยอด และการเดินสายไฟระหว่างบ้านเป็นเส้นเชื่อม หากกราฟดังกล่าวมีความเชื่อมโยงมาก (นั่นคือต้องลบจำนวนจุดยอดหรือเส้นเชื่อมมาก) ก็หมายความว่าถึงแม้จะมีสายไฟบางเส้นเสียไป ทั้งหมู่บ้านก็ยังมีไฟฟ้าใช้อยู่ ในขณะที่หากกราฟดังกล่าวมีความเชื่อมโยงน้อย ก็หมายความว่าสายไฟบางเส้นเสียไป อาจทำให้บางบ้านไม่มีไฟฟ้าใช้
ปัญหาการไหลในเครือข่ายมีความเกี่ยวข้องกับเรื่องความเชื่อมโยงของกราฟเป็นอย่างมาก
นิยามต่างๆ
[แก้]ส่วนนี้รอเพิ่มเติมข้อมูล คุณสามารถช่วยเพิ่มข้อมูลส่วนนี้ได้ |
Menger's theorem
[แก้]อ้างอิง
[แก้]- ↑ Diestel, R., Graph Theory, Electronic Edition, 2005, p 12.