ความต่อเนื่อง (ทฤษฎีกราฟ)

จากวิกิพีเดีย สารานุกรมเสรี

ในคณิตศาสตร์และวิทยาการคอมพิวเตอร์ เรื่องทฤษฎีกราฟ ความต่อเนื่อง หรือ ความเชื่อมโยง (อังกฤษ: Connectivity) เป็นคุณสมบัติหนึ่งของกราฟ โดยกราฟต่อเนื่อง หรือ กราฟเชื่อมโยง (Connected graph) หมายความว่ากราฟไม่ขาดจากกัน กล่าวคือ สำหรับทุกๆสองจุดยอดใดๆ จะสามารถไปถึงกันได้ หรือก็คือมีวิถีระหว่างจุดยอดทั้งสอง ในขณะที่กราฟไม่ต่อเนื่อง หรือ กราฟไม่เชื่อมโยง (Unconnected graph) หมายความว่ากราฟนั้นขาดออกจากกัน กล่าวคือมีอย่างน้อยสองจุดยอด ที่ไม่สามารถไปถึงกันได้ หรือก็คือไม่มีวิถีระหว่างจุดยอดทั้งสองจุดนั้น

ความต่อเนื่องของกราฟ ยังสามารถมองได้ในอีกแง่มุมหนึ่ง คือจำนวนของจุดยอดหรือเส้นเชื่อมที่น้อยที่สุด ที่ถ้าลบจุดยอดหรือเส้นเชื่อมเหล่านั้นทิ้งแล้ว กราฟดังกล่าวจะกลายเป็นกราฟไม่ต่อเนื่อง[1] จะเห็นว่าความต่อเนื่องของกราฟนั้นบ่งบอกถึงความแข็งแกร่ง/ความทนทานของกราฟ ตัวอย่างเช่นหากพิจารณาให้บ้านเป็นจุดยอด และการเดินสายไฟระหว่างบ้านเป็นเส้นเชื่อม หากกราฟดังกล่าวมีความต่อเนื่องมาก (นั่นคือต้องลบจำนวนจุดยอดหรือเส้นเชื่อมมาก) ก็หมายความว่าถึงแม้จะมีสายไฟบางเส้นเสียไป ทั้งหมู่บ้านก็ยังมีไฟฟ้าใช้อยู่ ในขณะที่หากกราฟดังกล่าวมีความต่อเนื่องน้อย ก็หมายความว่าสายไฟบางเส้นเสียไป อาจทำให้บางบ้านไม่มีไฟฟ้าใช้

ปัญหาการไหลในเครือข่ายมีความเกี่ยวข้องกับเรื่องความต่อเนื่องของกราฟเป็นอย่างมาก

นิยามต่างๆ[แก้]

Menger's theorem[แก้]

อ้างอิง[แก้]

  1. Diestel, R., Graph Theory, Electronic Edition, 2005, p 12.